algorithm - sucesiones - Almacene los 5000 números más grandes de una secuencia de números

secuencias de numeros para completar

Question

Dado el siguiente problema:

"Almacene los 5000 números más grandes de una secuencia de números"

La solución que viene a la mente es un árbol de búsqueda binario que mantiene un recuento de la cantidad de nodos en el árbol y una referencia al nodo más pequeño una vez que el recuento llega a 5000. Cuando el recuento alcanza 5000, cada nuevo número para agregar se puede comparar con el elemento más pequeño en el árbol. Si es mayor, se puede agregar el nuevo número, luego el más pequeño eliminado y el nuevo más pequeño calculado (que debería ser muy simple, ya teniendo el anterior más pequeño).

Mi preocupación con esta solución es que el árbol binario se sesgará de forma natural (ya que solo borro en un lado).

¿Hay alguna manera de resolver este problema que no creará un árbol terriblemente sesgado?

En caso de que alguien lo quiera, he incluido pseudocódigo para mi solución más abajo:

process(number)
{
  if (count == 5000 && number > smallest.Value)
  {
    addNode( root, number)
    smallest = deleteNodeAndGetNewSmallest ( root, smallest)
  }
}

deleteNodeAndGetNewSmallest( lastSmallest)
{
  if ( lastSmallest has parent)
  {
    if ( lastSmallest has right child)
    {
      smallest = getMin(lastSmallest.right)
      lastSmallest.parent.right = lastSmallest.right
    }
    else
    {
      smallest = lastSmallest.parent
    }
  }
  else 
  {
    smallest = getMin(lastSmallest.right)
    root = lastSmallest.right
  }
  count--
  return smallest
}

getMin( node)
{
  if (node has left)
    return getMin(node.left)
  else
    return node
}

add(number)
{
  //standard implementation of add for BST
  count++
}

Answer 1

Use una cola de prioridad (mínima). Agregue cada elemento entrante a la cola y cuando el tamaño llegue a 5,000 elimine el elemento mínimo (superior) cada vez que agrega un elemento entrante. La cola contendrá los 5,000 elementos más grandes y cuando la entrada se detenga, solo elimine los contenidos. Este MinPQ también se llama montón, pero es un término sobrecargado. Las inserciones y eliminaciones toman sobre log2 (N). Donde N alcanza un máximo de 5.000, esto sería un poco más de 12 [log2 (4096) = 12] veces la cantidad de elementos que está procesando.

Una excelente fuente de información es Algorithms, (4ª edición) de Robert Sedgewick y Kevin Wayne. Hay un excelente MOOC en coursera.org que se basa en este texto.

Answer 2

La solución más simple para esto es mantener un montón mínimo de tamaño máximo 5000.

• Cada vez que llega un nuevo número, comprueba si el montón es más pequeño que 5000, si es así, agrégalo.
• Si no es así, compruebe si el mínimo es más pequeño que el nuevo elemento, y si lo está, extráigalo e inserte el nuevo elemento en su lugar.
• Cuando hayas terminado, tienes un montón que contiene 5000 elementos más grandes.

Esta solución es O(nlogk) complejidad, donde n es la cantidad de elementos k es la cantidad de elementos que necesita (5000 en su caso).

También se puede hacer en O(n) usando el algoritmo de selección - almacenar todos los elementos, y luego encontrar el 5001º elemento más grande, y devolver todo lo que sea más grande. Pero es más difícil de implementar y para un tamaño de entrada razonable, podría no ser mejor. Además, si stream contiene duplicados, se necesita más procesamiento.