Heap (struttura dati): differenze tra le versioni

Versione delle 20:44, 18 nov 2019

Versione attuale delle 20:58, 22 giu 2025

(18 versioni intermedie di 14 utenti non mostrate)

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:

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 20 ⟶ 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 <kbd>true</kbd> se un heap è vuoto, <kbd>false</kbd> 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 37 ⟶ 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 48 ⟶ 54:

|cognome3= Rivest

|nome3= Ronald L.

|wkautore3=RonRonald Rivest

|titolo= Introduction to Algorithms

|anno= 1990

Riga 59 ⟶ 65:

{| class="wikitable"

|-

! Operazione

! Operation

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

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

Riga 66 ⟶ 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 88 ⟶ 94:

| inserimento

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

|style="background:#ffffddddffdd"| ''Θ''(log n1){{efn|name=amortized}}

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

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

Riga 96 ⟶ 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= https://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=https://web.eecs.umich.edu/~pettie/papers/focs05.pdf}}</ref>}}

|-

| unione

Riga 104 ⟶ 110:

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

|}

{{Gruppo di note}}

<references group="lower-alpha/>

== Applicazioni ==

Riga 115 ⟶ 121:

|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 153 ⟶ 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}}