Perché l'heap è migliore di un albero binario per rappresentare una coda prioritaria?

Question

In un heap (massimo) è facile trovare l'elemento più grande nel tempo O(1), ma per rimuoverlo effettivamente è necessaria la complessità di O(log(n)).

Quindi, se l'inserimento e la cancellazione da un heap sono entrambi O(log(n)), quali sono i vantaggi di un heap su un albero binario per rappresentare una coda di priorità?

Answer 1

1. Gli heap utilizzano meno memoria. Possono essere implementati come array e quindi non c'è un sovraccarico per la memorizzazione dei puntatori. (Un albero binario può essere implementato come una matrice, ma è probabile che ci siano molte "lacune" vuote che potrebbero sprecare anche più spazio di quanto non siano implementate come nodi con i puntatori).

2. Gli heap sono garantiti per l'altezza del log (n), poiché non è necessario garantire che gli elementi possano essere recuperati in ordine ordinato attraverso un traversamento in ordine, solo che il valore di un nodo domina i valori dei propri figli. Ciò consente loro di avere la loro struttura "compressa" come una matrice. Un albero binario (a meno che non sia un albero binario bilanciato) di solito finirà con rami che hanno un'altezza maggiore di log (n), quindi anche se le operazioni hanno la stessa grande complessità O, in realtà l'heap sarà leggermente più veloce.

3. Poiché l'heap può essere implementato come matrice, si ottiene un enorme vantaggio dell'accesso alla memoria contigua che è probabilmente ancora nella cache piuttosto che accedere ai nodi indicati da puntatori la cui memoria è sparsa dappertutto.

4. Cumuli sono più semplici da implementare rispetto alberi binari (alberi binari in particolare bilanciati)

Uno svantaggio è che con cumuli che non sono in grado di fare una ricerca binaria, ma per una coda di priorità non lo fai bisogno di questa capacità