Esiste un algoritmo O (n) per costruire un max-heap?

Question

Dato un array di numero, c'è un algoritmo O (n) per costruire un max-heap?

Answer 1

Non credo. Penso che il meglio che puoi fare sia O (log n) o un po 'meglio con qualcosa come un ammasso di fibrosi.

Answer 2

Suggerimento: supponiamo che al posto di un array sia stato assegnato un albero binario arbitrario. Riesci a pensare a un modo efficace per correggere tutti i nodi che non soddisfano la proprietà heap?

Answer 3

Se si utilizza uno Fibonacci Heap si ottiene amortized O (1) inserimento. Di conseguenza, è possibile creare un heap massimo in O (n) ammortizzato da un array.

L'attuazione di tale, lascio come esercizio *.

_{* Tuttavia, ci sono implementazioni di esempio collegate sulla pagina di Wikipedia.}

Answer 4

Sì, c'è: Building a heap.

Answer 5

Sì, come in questo codice:

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

(push_heap è una funzione che accetta un puntatore ad un cumulo e la dimensione heap e spinge la parte superiore del mucchio finché le condizioni mucchio siano rispettate o il nodo raggiunge il fondo del mucchio).

Per ottenere il motivo per cui questo è O (N) guardare l'albero binario completo:

• 1/2 elementi (ultimo livello, i> N/2) sono spinti verso il basso al massimo 0 punti -> N/2 * 0 operazioni
• 1/4 elementi (ultimo livello 1, i> N/4) vengono premuti al massimo 1 passo -> N/4 * 1 operazioni

• 1/8 elementi (ultimo- 2 livelli, i> N/8) sono premuti al massimo 2 passi -> N/8 * 2 operazioni ...

  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 
  

Spero che la matematica non sia davvero troppo complicata. Se guardi sull'albero e aggiungi quanto può essere spinto verso il basso ciascun nodo, vedrai il limite superiore O (N).