tienda los mayores 5000 números de una serie de números

Dado el siguiente problema:tienda los mayores 5000 números de una serie de números

"tienda de los mayores 5000 números de una serie de números"

La solución que viene a la mente es una árbol binario de búsqueda manteniendo un recuento del número de nodos en el árbol y una referencia al nodo más pequeño una vez que el recuento alcanza 5000. Cuando el recuento alcanza 5000, cada nuevo número para agregar se puede comparar con el elemento más pequeño del á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 estoy borrando por un lado).

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

En caso de que alguien lo quiere, he incluido pseudo-código para mi solución en lo que va a continuación:

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++ 
}

Fuente

2012-05-25 Richard

Puede usar un árbol de búsqueda equilibrado como AVL o similar (https://en.wikipedia.org/wiki/AVL_tree). Pero una solución basada en montones es más natural. –

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

Cada vez que llega un nuevo número, compruebe si el montón es más pequeño que 5000, si lo está, agréguelo.
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 con 5000 elementos más grandes.

Esta solución es O(nlogk) complejidad, donde n es el número de elementos y k es el número de elementos que necesita (5000 en su caso).

Se puede hacer también en O(n) usando selection algorithm - almacene todos los elementos, y luego encuentre el 5001mo elemento más grande, y devuelva 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.

Fuente

2012-05-25 09:36:49 amit

+1 para el algoritmo de selección. Solo quiero agregar: STL C++ tiene implementación para esto. Sin embargo, no estoy seguro acerca de Java. Sin embargo, este método de cálculo fuera de línea necesita una complejidad de espacio O (n). – nhahtdh

Excelente punto acerca del algoritmo de selección. OTOH esto exige O (n) memoria. – valdo

Puede usar el algoritmo de selección para encontrar los elementos k superiores, pero solo usa la memoria O (k) almacenando una matriz de 2k elementos. Cada vez que llene la matriz, use el algoritmo de selección para dejar caer la k más baja. Esto se traduce en tomar O (n) tiempo independientemente del valor de k, ya que está haciendo algoritmos de selección O (n/k), cada uno de los cuales toma tiempo O (k). También solo usa memoria O (k). – templatetypedef

Utilice 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.

Fuente

2013-11-01 16:31:03 user1295785

tienda los mayores 5000 números de una serie de números

Respuesta

Cuestiones relacionadas