Algoritmo per la fusione di due heap massimi?

Question

Esiste un algoritmo efficiente per l'unione di 2 max-heap archiviati come array?

Answer 1

Dipende dal tipo di heap.

Se si tratta di un heap standard in cui ogni nodo ha fino a due figli e che viene riempito con le foglie su un massimo di due righe diverse, non è possibile ottenere risultati migliori di O (n) per l'unione.

Basta mettere insieme i due array e creare un nuovo heap da essi che richiede O (n).

Per prestazioni di fusione migliori, è possibile utilizzare un'altra variante di heap come un Fibonacci-Heap che può essere unito in O (1) ammortizzato.

Aggiornamento: noti che è peggio inserire tutti gli elementi del primo mucchio ad uno per il secondo mucchio o viceversa poiché un inserimento richiederà O (log (n)). Come il tuo commento Stati, non sembri sapere come il mucchio è ottimamente costruito all'inizio (ancora per un heap binario di serie)

1. Creare un array e mettere negli elementi di entrambi i cumuli in qualche arbitraria L'ordine
2. ora inizia al livello più basso. Il livello più basso contiene banchine di dimensioni massime pari a 1, quindi questo livello viene eseguito
3. sposta un livello in alto. Quando la condizione di heap di uno dei "sotto-heap" viene violata, scambia la radice del "sotto-heap" con il figlio più grande. Successivamente, viene eseguito il livello 2
4. passare al livello 3. Quando le condizioni dell'heap vengono violate, elaborare come prima. Scambialo con il figlio più grande e ricorri in modo ricorsivo finché tutto corrisponde al livello 3
5. ...
6. quando raggiungi la cima, hai creato un nuovo heap in O (n).

Tralascio una prova qui, ma si può spiegare questo dato che avete fatto la maggior parte del mucchio sui livelli inferiori dove non c'era bisogno di scambiare molto contenuti per ristabilire i vincoli dello heap. Hai operato su "sotto-heap" molto più piccoli, che è molto meglio di quello che faresti se dovessi inserire ogni elemento in uno degli heap => allora, ti opereresti ogni volta sull'intero heap che prende O (n) ogni volta .

Aggiornamento 2: Un heap binomiale consente l'unione in O (log (n)) e sarebbe conforme al requisito O (log (n)^2).

Answer 2

Due cumuli binari di dimensioni n e k possono essere uniti in confronti O (log n * log k). Vedo

Jörg-R. Sack and Thomas Strothotte, An algorithm for merging heaps, Acta Informatica 22 (1985), 172-186.

Answer 3

Penso che quello che stai cercando in questo caso è un binomio Heap.

Un heap binomiale è una raccolta di alberi binomiali, un membro della famiglia di heap in grado di unire. Il tempo di esecuzione nel caso peggiore per un'unione (unione) su 2+ heap binomiali con n elementi totali negli heap è O (lg n).

Vedere http://en.wikipedia.org/wiki/Binomial_heap per ulteriori informazioni.