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).
• 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).
• 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 O(f) è l'upper-bound asintotico, mentre Θ(f) è l'esatto ordine di grandezza. La struttura si assume essere di tipo "min heap".

Operazione	Binario	Binomiale	Fibonacci	Pairing
ricerca minimo	Θ(1)	Θ(1)	Θ(1)	Θ(1)
rimozione minimo	Θ(log n)	Θ(log n)	O(log n)	O(log n)
inserimento	Θ(log n)	Θ(1)	Θ(1)	Θ(1)
decremento della chiave	Θ(log n)	Θ(log n)	Θ(1)	o(log n)
unione	Θ(m log n)	O(log n)	Θ(1)	Θ(1)

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.
• 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.

Voci correlate

• Heapsort
• Pila (informatica)
• Coda (informatica)
• Albero (informatica)
• Treap

Altri progetti

Altri progetti

• Wikimedia Commons

• 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) heap, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL