Heap (struttura dati): differenze tra le versioni

Versione delle 20:23, 18 apr 2020

Versione delle 15:21, 20 nov 2020

Riga 5:

* min-heap: se <math>v[Padre(j)] < v[j], \forall j</math>

* max-heap: se <math>v[Padre(j)] > v[j], \forall j</math>

In questo modo si garantisce che compiendo un qualsiasi percorso che parte da un nodo dell'albero e scendendo nella struttura verso le foglie, si attraversano nodi con chiave sempre maggiore della ldell'ultima foglia visitata. La scelta di utilizzare un tipo di heap anziché l'altro è data dal tipo di impiego che se ne vuole fare. Da notare che, come si vede nel grafo a fianco, non è implicato alcun ordine specifico tra nodi fratelli o cugini, ovvero, i nodi non sono ordinati trasversalmente (come invece accade, ad esempio, nell'[[albero binario di ricerca]]).

Gli heap sono essenziali negli [[algoritmi]] della [[teoria dei grafi]] (come l'[[algoritmo di Dijkstra]]) o negli algoritmi di ordinamento come l'[[heapsort]]. Un'implementazione molto comune di un heap è l'[[heap binario]], basato su un [[albero binario]] completo (come quello in figura). L'heap è, inoltre, una delle implementazioni più efficienti di un [[tipo di dato astratto]] chiamato [[coda di priorità]].