¿Hay un algoritmo O (n) para construir un montón máximo?

Question

Dado un conjunto de números, ¿existe un algoritmo O (n) para construir un montón máximo?

Answer 1

No lo creo. Creo que lo mejor que puedes hacer es O (log n) o un poco mejor con algo así como un montón de fib.

Answer 2

Sugerencia: supongamos que en lugar de una matriz se le haya asignado un árbol binario arbitrario. ¿Puedes pensar en una forma eficiente de arreglar los nodos que no satisfacen la propiedad de montón?

Answer 3

Si usa Fibonacci Heap obtiene amortized O (1) inserción. En consecuencia, puede construir un montón máximo en O (n) amortizado desde una matriz.

La implementación de tal, lo dejo como un ejercicio *.

_{* Sin embargo, hay implementaciones de ejemplos vinculados en la página de Wikipedia.}

Answer 4

Sí, hay Building a heap.

Answer 5

Sí, como en este código:

for (int i = N/2; i >= 0; --i) 
    push_heap(heap + i, N - i); 

(push_heap es una función que acepta un puntero a un montón y el tamaño del montón y empuja la parte superior de la pila hasta que se respetan o de las condiciones del montón el nodo alcanza el fondo del montón).

Para llegar por qué esto es O (N) mira el árbol binario completo:

• 1/2 elementos (último nivel, i> N/2) se empujan hacia abajo en la mayoría de los pasos 0 -> N/2 * 0 operaciones
• 1/4 elementos (último-1 nivel, i> N/4) se empujan hacia abajo a lo sumo 1 paso -> N/4 * 1 operaciones

• 1/8 elementos (última- 2 niveles, i> N/8) se presionan hacia abajo como máximo 2 pasos -> N/8 * 2 operaciones ...

  N/4 * 1 + N/8 * 2 + N/16 * 3 + ... = 
  
      N/4 * 1 + N/8 * 1 + N/16 * 1 + ... + 
        N/8 * 1 + N/16 * 2 + ... = 
  
      N/4 * 1 + N/8 * 1 + N/16 * 1 + ... + // < N/2 
        N/8 * 1 + N/16 * 1 + ... + // < N/4 
           N/16 * 1 + ... + // < N/8 
             ... = // N/2 + N/4 + N/8 + ... < N 
  

Espero que las matemáticas no sean realmente muy complicadas. Si miras en el árbol y agregas cuánto se puede empujar cada nodo, verás el límite superior O (N).