Heap

Da Wikipedia, l'enciclopedia libera.
Nota disambigua.svg Disambiguazione – Se stai cercando lo spazio di memoria allocato dinamicamente in RAM, vedi Gestione della memoria.
Esempio di un max heap binario con nodi da 1 a 100

In informatica, un heap è una struttura dati basata sugli alberi che soddisfa la "proprietà di heap": se A è un genitore di B, allora la chiave di A è ordinata rispetto alla chiave di B conformemente alla relazione d'ordine applicata all'intero heap. Di conseguenza, gli heap possono esse 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. 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 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 l'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à.

Operazioni[modifica | modifica wikitesto]

Le operazioni comuni negli heap sono:

Basiche
  • 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 di 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: ritorna il numero di elementi di un heap.
  • is-empty: ritorna 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. Il nome "sift" deriva da "sieve" ("setaccio").
  • sift-down: sposta un nodo in basso all'interno dell'albero; utilizzato per ripristinare la condizione di heap dopo la rimozione o sostituzione.

Implementazione[modifica | modifica wikitesto]

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 ad un nodo della heap, si definiscono padre di j il nodo in posizione j/2, figlio sinistro di j il nodo in posizione j*2 e figlio destro di j il nodo in posizione j*2+1.

Analisi asintotica[modifica | modifica wikitesto]

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

Operation Binario[3] Binomiale[3] Fibonacci[3] Pairing[4]
ricerca minimo Θ(1) Θ(1) Θ(1) Θ(1)
rimozione minimo Θ(log n) Θ(log n) O(log n)[lower-alpha 1] O(log n)[lower-alpha 1]
inserimento Θ(log n) Θ(1)[lower-alpha 1] Θ(1) Θ(1)
decremento della chiave Θ(log n) Θ(log n) Θ(1)[lower-alpha 1] o(log n)[lower-alpha 1][lower-alpha 2]
unione Θ(m log n)[lower-alpha 3] O(log n)[lower-alpha 4] Θ(1) Θ(1)
  1. ^ a b c d e Analisi ammortizzata.
  2. ^ Con lower-bound \Omega(\log\log n) e upper-bound O(2^{2\sqrt{\log\log n}})[5][6]
  3. ^ n è la dimensione dell'heap maggiore e m è la dimensione dell'heap minore.
  4. ^ n è la dimensione dell'heap maggiore.

Applicazioni[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

  • 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[modifica | modifica wikitesto]

  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
  3. ^ 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.
  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.
  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.
  6. ^ (EN) Seth Pettie, Towards a Final Analysis of Pairing Heaps (PDF), in Max Planck Institut für Informatik, 2005.
  7. ^ (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.

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

  • (EN) Heap su Wolfram MathWorld