Heap (struttura dati): differenze tra le versioni

Versione delle 20:18, 21 mar 2016

Versione attuale delle 20:58, 22 giu 2025

(27 versioni intermedie di 20 utenti non mostrate)

Riga 1:

{{nota disambigua|lo spazio di memoria allocato dinamicamente in RAM|Gestione della memoria}}

[[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 esseessere 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:

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]]).

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

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à]].

* 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 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à]]. 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''

;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''<ref>{{en}} The Python Standard Library, 8.4. heapq — Heap queue algorithm, [https://docs.python.org/2/library/heapq.html#heapq.heappush heapq.heappush]</ref>).

Riga 21 ⟶ 26:

;Creazione

*''create-heap'': crea un heap vuoto.

*''heapify'': crea un heap a partire dida 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'': ritornarestituisce il numero di elementi di un heap.

*''is-empty'': ritornarestituisce <ttkbd>true</ttkbd> se un heap è vuoto, <ttkbd>false</ttkbd> 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''"significa ("[[setaccio]]setacciare").

*''sift-down'': sposta un nodo in basso all'interno dell'albero; utilizzato per ripristinare la condizione di heap dopo la rimozione o sostituzione.

Riga 38 ⟶ 43:

Gli heap sono generalmente implementati tramite array (di dimensione fissa, o [[Array dinamico|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 binario|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 ''<math>j''</math>, indice ada un nodo della heap a partire da <math>j=1</math>, si definiscono padre di ''<math>j''</math> il nodo in posizione <math>\left\lfloor \frac{j/}{2}\right\rfloor</math> (dove <math>\lfloor x\rfloor</math> è la funzione [[parte intera]] di <math>x</math>), figlio sinistro di ''<math>j''</math> il nodo in posizione <math>j*22j</math> e figlio destro di ''<math>j''</math> il nodo in posizione <math>j*22j+1</math>.

== Analisi asintotica ==

Riga 49 ⟶ 54:

|cognome3= Rivest

|nome3= Ronald L.

|wkautore3=RonRonald Rivest

|titolo= Introduction to Algorithms

|anno= 1990

Riga 60 ⟶ 65:

{| class="wikitable"

|-

! Operazione

! Operation

! [[Heap binario|Binario]]<ref name="CLRS"/>

! [[Heap binomiale|Binomiale]]<ref name="CLRS"/>

Riga 67 ⟶ 72:

|contributo= Improved upper bounds for pairing heaps

| doi = 10.1007/3-540-44985-X_5

|pp= 63–7763-77

|editore= Springer-Verlag

|serie= Lecture Notes in Computer Science

Riga 97 ⟶ 102:

|style="background:#ffffdd"| ''Θ''(log ''n'')

|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}

|style="background:#ffffdd"| ''o''(log ''n''){{efn|name=amortized}}{{efn|name=pairingdecreasekey|Con lower-bound <math>\Omega(\log\log n)</math> e upper-bound <math>O(2^{2\sqrt{\log\log n}})</math><ref name="Fredman And Tarjan">{{Cita pubblicazione|nome1=Michael Lawrence|cognome1=Fredman|wkautore1=Michael Fredman|nome2=Robert E.|cognome2=Tarjan|wkautore2=Robert Tarjan |titolo=Fibonacci heaps and their uses in improved network optimization algorithms|url= httphttps://www.cl.cam.ac.uk/~sos22/supervise/dsaa/fib_heaps.pdf |lingua= en |formato= PDF |rivista=[[Journal of the Association for Computing Machinery]]|volume=34|anno=1987|pp=596–615596-615|cid=harv|doi=10.1145/28869.28874|numero=3}}</ref><ref>{{Cita pubblicazione|cognome=Pettie|nome=Seth|titolo=Towards a Final Analysis of Pairing Heaps|rivista=Max Planck Institut f&uuml;r Informatik|anno=2005|lingua=en|url=httphttps://web.eecs.umich.edu/~pettie/papers/focs05.pdf}}</ref>}}

|-

| unione

Riga 105 ⟶ 110:

|style="background:#ddffdd"| ''Θ''(1)

|}

{{Gruppo di note}}

<references group="lower-alpha/>

== 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.<ref>
{{Cita pubblicazione
|cognome= Frederickson
|nome= Greg N.

|contributo= An Optimal Algorithm for Selection in a Min-Heap

| doi = 10.1006/inco.1993.1030

|pp= 197–214197-214

|lingua= en

|editore= Academic Press

Riga 120 ⟶ 128:

|numero= 2

|anno= 1993

|url= http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf}}</ref>

|accesso= 6 novembre 2015

|urlarchivio= https://web.archive.org/web/20121203045606/http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf

|dataarchivio= 3 dicembre 2012

|urlmorto= sì

}}

</ref>

*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 [[Coda di priorità|code di priorità]] è tramite heap.

Riga 126 ⟶ 140:

== Implementazioni ==

*La libreria standard [[C++]] fornisce gli algoritmi <ttkbd>make_heap</ttkbd>, <ttkbd>push_heap</ttkbd> e <ttkbd>pop_heap</ttkbd> per gli heaps (di solito implementati come heap binari), che operano su [[Iteratore|iteratori]] ad accesso casuale.

*Fra le librerie C++ [[Boost (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 (linguaggio di programmazione)|Java]] (dalla versione 1.5) fornisce gli heap binari con la classe [httphttps://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html <ttkbd>java.util.PriorityQueue&lt;E&gt;</ttkbd>] della [[Java Collections Framework]]. Non supporta le operazioni di incremento e decremento.

*[[Python]] ha un modulo [https://docs.python.org/library/heapq.html <ttkbd>heapq</ttkbd>] che implementa una coda di priorità tramite un albero binario.

*[[PHP]] supporta sia max-heap (<ttkbd>SplMaxHeap</ttkbd>) che min-heap (<ttkbd>SplMinHeap</ttkbd>) dalla versione 5.3 della Standard PHP Library.

*[[Perl]] supporta le implementazioni di heap binari, binomiali e di Fibonacci nella distribuzione [https://metacpan.org/module/Heap <ttkbd>Heap</ttkbd>] disponibile su [[CPAN]].

*La libreria [[Core Foundation]] Apple contiene la struttura [https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBinaryHeapRef/Reference/reference.html <ttkbd>CFBinaryHeap</ttkbd>].

== Note ==

Riga 145 ⟶ 159:

== Altri progetti ==

{{interprogetto|preposizione=sull'|wikt=heap}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

*{{en}} [http://mathworld.wolfram.com/Heap.html Heap] su Wolfram MathWorld

* {{FOLDOC||heap}}

{{strutture dati}}