Heap (struttura dati)

Esempio di un max heap binario con nodi da 1 a 100

In informatica, un heap (lett. "mucchio") è una struttura dati basata sugli 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 $v[Padre(j)]<v[j],\forall j$
max-heap: se $v[Padre(j)]>v[j],\forall j$

In particolare, da un punto di vista di array, descriviamo gli indici assunti da heap per i vari nodi:

padre = $i/2$
nodo sinistro (left): $2i$
nodo destro (right) $2i+1$

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

Le operazioni comuni negli heap sono:

Basilari

find-max o find-min: trova l'elemento con chiave maggiore di un max-heap o l'elemento con chiave minore di un min-heap.
insert: aggiungi un nuovo elemento all'heap (a.k.a., push^[1]).
extract-min o extract-max: ritorna il nodo del valore minimo di un min heap (o massimo di un max heap) dopo averlo rimosso dalla struttura (a.k.a., pop^[2]).
delete-max o delete-min: rimuove l'elemento radice di un max/min heap, rispettivamente.
replace: esegue il pop sulla radice e il push di una nuova chiave.

Creazione

create-heap: crea un heap vuoto.
heapify: crea un heap a partire da un array.
merge (union): unisce due heap per formare un nuovo heap valido contenente tutti gli elementi di entrambi mantenendo gli heap originali.
meld: unisce due heap per formare un nuovo heap valido contenente tutti gli elementi di entrambi, eliminando gli heap originali.

Inspection

size: restituisce il numero di elementi di un heap.
is-empty: restituisce true se un heap è vuoto, false altrimenti.

Altre

increase-key o decrease-key: aumenta/decrementa il valore di una chiave di un max/min heap, rispettivamente.
delete: rimuove un nodo arbitrario.
sift-up: sposta un nodo in alto all'interno dell'albero; utilizzato per ripristinare la condizione di heap dopo l'inserimento. "sift" significa "setacciare".
sift-down: sposta un nodo in basso all'interno dell'albero; utilizzato per ripristinare la condizione di heap dopo la rimozione o sostituzione.

Implementazione

Gli heap sono generalmente implementati tramite array (di dimensione fissa, o variabile) e non richiede puntatori fra gli elementi. Dopo la rimozione, inserimento o sostituzione di un elemento, la proprietà di heap potrebbe essere violata, rendendo necessario il bilanciamento tramite operazioni interne.

Gli heap binari possono essere rappresentati in un modo molto efficiente (dal punto di vista dello spazio) utilizzando un solo array. Il primo elemento rappresenta la radice. I due elementi seguenti contengono i figli della radice. I quattro seguenti contengono i figli dei figli, e così via. In generale, dato $j$ , indice a un nodo della heap a partire da $j=1$ , si definiscono padre di $j$ il nodo in posizione $\left\lfloor {\frac {j}{2}}\right\rfloor$ (dove $\lfloor x\rfloor$ è la funzione parte intera di $x$ ), figlio sinistro di $j$ il nodo in posizione $2j$ e figlio destro di $j$ il nodo in posizione $2j+1$ .

Analisi asintotica

Nelle seguenti complessità temporali^[3] O(f) è l'upper-bound asintotico, mentre Θ(f) è l'esatto ordine di grandezza. La struttura si assume essere di tipo "min heap".

Operazione	Binario^[3]	Binomiale^[3]	Fibonacci^[3]	Pairing^[4]
ricerca minimo	Θ(1)	Θ(1)	Θ(1)	Θ(1)
rimozione minimo	Θ(log n)	Θ(log n)	O(log n)^{[N 1]}	O(log n)^{[N 1]}
inserimento	Θ(log n)	Θ(1)^{[N 1]}	Θ(1)	Θ(1)
decremento della chiave	Θ(log n)	Θ(log n)	Θ(1)^{[N 1]}	o(log n)^{[N 1]}^{[N 2]}
unione	Θ(m log n)^{[N 3]}	O(log n)^{[N 4]}	Θ(1)	Θ(1)

^ ^a ^b ^c ^d ^e Analisi ammortizzata.
^ Con lower-bound $\Omega (\log \log n)$ e upper-bound $O(2^{2{\sqrt {\log \log n}}})$ ^[5]^[6]
^ n è la dimensione dell'heap maggiore e m è la dimensione dell'heap minore.
^ n è la dimensione dell'heap maggiore.

Applicazioni

L'heap ha diverse applicazioni:

Algoritmi di ordinamento: l'heapsort è uno dei migliori metodi di ordinamento, essendo in-place e senza upper-bound quadratico.
Algoritmi di selezione: un heap permette di accedere all'elemento con chiave minima o massima in tempo costante, e le altre selezioni (come la media o il k-esimo elemento) possono essere svolte in tempo sub-lineare.^[7]
Algoritmi sui grafi: l'heap trova applicazione in svariati metodi, come l'algoritmo di Prim per la ricerca dell'albero ricoprente minimo o l'algoritmo di Dijkstra per la ricerca del cammino minimo.
Code di priorità: uno dei modi di implementare le code di priorità è tramite heap.
Statistica d'ordine: l'heap può essere usato per trovare efficientemente il k-esimo elemento minore (o maggiore) in un array.

Implementazioni

La libreria standard C++ fornisce gli algoritmi make_heap, push_heap e pop_heap per gli heaps (di solito implementati come heap binari), che operano su iteratori ad accesso casuale.
Fra le librerie C++ Boost c'è una libreria di heap. Al contrario della STL, quest'ultima supporta anche le operazioni di incremento e decremento, e supporta tipi addizionali di heap: nello specifico, supporta gli heap d-ari, binomiali, di Fibonacci, pairing e skew.
Il linguaggio Java (dalla versione 1.5) fornisce gli heap binari con la classe java.util.PriorityQueue<E> della Java Collections Framework. Non supporta le operazioni di incremento e decremento.
Python ha un modulo heapq che implementa una coda di priorità tramite un albero binario.
PHP supporta sia max-heap (SplMaxHeap) che min-heap (SplMinHeap) dalla versione 5.3 della Standard PHP Library.
Perl supporta le implementazioni di heap binari, binomiali e di Fibonacci nella distribuzione Heap disponibile su CPAN.
La libreria Core Foundation Apple contiene la struttura CFBinaryHeap.

Note

^ (EN) The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappush
^ (EN) The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappop
^ ^a ^b ^c ^d (EN) Thomas H. Cormen, Charles E. Leiserson e Ronald L. Rivest, Introduction to Algorithms, 1ª ed., MIT Press and McGraw-Hill, 1990, ISBN 0-262-03141-8.
^ (EN) John Iacono, Improved upper bounds for pairing heaps, in Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, 2000, pp. 63–77, DOI:10.1007/3-540-44985-X_5.
^ (EN) Michael Lawrence Fredman e Robert E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms (PDF), in Journal of the Association for Computing Machinery, vol. 34, n. 3, 1987, pp. 596–615, DOI:10.1145/28869.28874.
^ (EN) Seth Pettie, Towards a Final Analysis of Pairing Heaps (PDF), in Max Planck Institut für Informatik, 2005.
^ (EN) Greg N. Frederickson, An Optimal Algorithm for Selection in a Min-Heap (PDF), in Information and Computation, vol. 104, n. 2, Academic Press, 1993, pp. 197–214, DOI:10.1006/inco.1993.1030. URL consultato il 6 novembre 2015 (archiviato dall'url originale il 3 dicembre 2012).

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file sull'heap

Collegamenti esterni

heap, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
(EN) Eric W. Weisstein, Heap, su MathWorld, Wolfram Research.
(EN) Denis Howe, heap, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Portale Informatica

Portale Matematica

[amortized-5] Analisi ammortizzata.

[pairingdecreasekey-8] Con lower-bound $\Omega (\log \log n)$ e upper-bound $O(2^{2{\sqrt {\log \log n}}})$ ^[5]^[6]

[merge2-9] è la dimensione dell'heap maggiore e m è la dimensione dell'heap minore.

[merge-10] è la dimensione dell'heap maggiore.

[1] (EN) The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappush

[2] (EN) The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappop

[CLRS-3] (EN) Thomas H. Cormen, Charles E. Leiserson e Ronald L. Rivest, Introduction to Algorithms, 1ª ed., MIT Press and McGraw-Hill, 1990, ISBN 0-262-03141-8.

[Iacono-4] (EN) John Iacono, Improved upper bounds for pairing heaps, in Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, 2000, pp. 63–77, DOI:10.1007/3-540-44985-X_5.

[Fredman_And_Tarjan-6] (EN) Michael Lawrence Fredman e Robert E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms (PDF), in Journal of the Association for Computing Machinery, vol. 34, n. 3, 1987, pp. 596–615, DOI:10.1145/28869.28874.

[7] (EN) Seth Pettie, Towards a Final Analysis of Pairing Heaps (PDF), in Max Planck Institut für Informatik, 2005.

[11] (EN) Greg N. Frederickson, An Optimal Algorithm for Selection in a Min-Heap (PDF), in Information and Computation, vol. 104, n. 2, Academic Press, 1993, pp. 197–214, DOI:10.1006/inco.1993.1030. URL consultato il 6 novembre 2015 (archiviato dall'url originale il 3 dicembre 2012).

[1]

[2]

[3]

[4]

[N 1]

[N 2]

[N 3]

[N 4]

[5]

[6]

[7]

V · D · M Strutture dati
Tipi	Collezione · Container
Astratte	Array associativo (Multimap) · Lista · Pila · Coda (Deque) · Coda di priorità · Set (Multiset · Mfset)
Array	Bit array · Buffer circolare · Array dinamico · Hash table · Array sparso
Collegate	Lista di associazioni · Lista concatenata · Skip list · Unrolled linked list · Lista concatenata tramite XOR
Alberi	B-albero · Albero binario di ricerca (Albero AA · Albero AVL · RB-Albero · Albero binario di ricerca bilanciato · Albero splay) · Heap (Heap binario · Heap binomiale · Heap di Fibonacci) · Albero di Merkle · Albero SPQR · Albero PQ · Albero indicizzato binario
Grafi	Diagramma binario di decisione · Digrafo aciclico · Automa a stati finiti deterministico aciclico
Alberi di partizionamento dei dati spaziali	Albero quadramentale · M-tree · R-tree (R* tree · R+ tree) · X-tree
Lista di strutture dati