Heap (struttura dati): differenze tra le versioni

Versione delle 11:17, 16 giu 2021

Versione delle 00:09, 9 gen 2022

Riga 1:

[[File:Max-Heap.svg|thumb|right|Esempio di un max heap [[Albero binario|binario]] con nodi da 1 a 100]]

In [[informatica]], un '''heap''' (lett. "mucchio") è una [[struttura dati]] basata sugli [[Albero (informatica)|alberi]] che soddisfa la "proprietà di heap": se A è un genitore di B, allora la chiave (il valore) di A è ordinata rispetto alla chiave di B conformemente alla relazione d'ordine applicata all'intero heap. Di conseguenza, gli heap possono essere suddivisi in "'''max heap'''" e "'''min heap'''". In un max heap, le chiavi di ciascun nodo sono sempre maggiori o uguali di quelle dei figli, e la chiave dal valore massimo appartiene alla radice (detta anche nodo root). In un min heap, le chiavi di ciascun nodo sono sempre minori o uguali di quelle dei figli, e la chiave dal valore minimo appartiene alla radice.

Quindi, dato un heap ''v'' ed un indice di posizione ''j'', ''v'' si dice

* 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 particolare, da un punto di vista di array, descriviamo gli indici assunti da heap per i vari nodi:

* padre = <math>i/2</math>

* nodo sinistro (left): <math>2i</math>

* nodo destro (right) <math>2i + 1</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 dell'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à]]. Essi vengono inoltre utilizzati negli algoritmi di selezione o il merge per l'elemento k-esimo, prendendo gli stream di input e convertendoli ordinatamente in stream di output.

== Operazioni ==