Heap binario: differenze tra le versioni

Versione delle 19:43, 16 set 2015

Versione attuale delle 19:53, 2 feb 2025

(39 versioni intermedie di 12 utenti non mostrate)

Riga 1:

{{Nota disambigua|l'area di memoria heap|Allocazione dinamica della memoria}}

{{F|programmazione|febbraio 2013}}

{{Avvisounicode}}

{{Strutture dati lineari}}

[[File:HeapVector.PNG|thumb|Implementazione di un heap (min-heap) mediante Vettore]]

UnUno '''heap binario''', è unauno [[Heap (struttura dati)|heap]] utilizzatasviluppato in [[informatica]], più precisamente un vettore o una lista che soddisfi la proprietà heap. Un heap binario può essere visto, per comodità di rappresentazione, comesu un [[albero binario]] quasi completo. È usato principalmente per la raccolta di collezioni di dati, dette dizionari, e per la rappresentazione di [[code di priorità]]. Lo heap binario deve sottostare alle seguenti condizioni:

*Condizione 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. In parole più semplici, se il nodo A è genitore del nodo B, allora il nodo A ha maggior priorità di B. Uno heap binario può essere definito in modo che le chiavi più prioritarie siano quelle più piccole (si parla di ''heap a minimo'') oppure in modo che le chiavi più prioritarie siano le più grandi (''heap a massimo'').

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. Si possono quindi definire le funzioni Padre(j), FiglioSX(j), FiglioDX(j) che rispettivamente restituiscono l'indice del padre, del figlio sinistro e del figlio destro di j. Spesso sono implementate come macro o funzioni in linea.

*Condizione di forma: tutti i livelli dello heap, tranne eventualmente l'ultimo, devono essere completi; se l'ultimo livello non è completo, i nodi devono essere disposti —per convenzione— a partire dall'estrema sinistra. Questo significa che, nell'ultimo livello, i nodi vengono aggiunti nel primo spazio vuoto a partire dalla sinistra.

Esistono due tipi di heap: '''min-heap''' e '''max-heap'''. La scelta di utilizzare un tipo di heap anziché l'altro è data dal tipo di impiego che se ne vuole fare.

== Implementazione con array ==

Condizioni '''Heap''': dato j indice di posizione della struttura e v lo heap preso in considerazione

Dato <var>j</var>, indice ad un nodo della heap, si ha che:

* min-heap: se '''v[Padre(j)] < v[j]'''

* il padre di <var>j</var> è il nodo in posizione <math>j/2</math>

* max-heap: se '''v[Padre(j)] > v[j]'''

* il figlio sinistro di <var>j</var> è il nodo in posizione <math>2*j</math>

* il figlio destro di <var>j</var> è il nodo in posizione <math>2*j+1</math>

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. Si possono quindi definire le funzioni <samp>Padre(j)</samp>, <samp>FiglioSX(j)</samp>, <samp>FiglioDX(j)</samp> che rispettivamente restituiscono l'indice del padre, del figlio sinistro e del figlio destro di <var>j</var>. Spesso sono implementate come macro o funzioni in linea.

Nell'immagine in alto a fiancodestra è possibile osservare quanto descritto, in aggiunta si può dire che viene definito come ''last'' (ultimo) l'elemento che si trova più a destra nel livello delle foglie. Nell'esempio last ha valore 15. Questo particolare nodo assume un compito determinante nei metodi per la rimozione della chiave minima (che è ovvio supporre, per le proprietà citate, si trovi nella radice) e nell'inserimento di una nuova chiave.

Da qui se ne deduce quindi che una min-heap possiede sempre l'elemento minore alla radice, mentre una max-heap possiede sempre l'elemento maggiore alla radice. Si noti che non c'è un ordine tra i fratelli di un nodo e/o i cugini (come invece c'è nell'[[albero binario]]).

== Operazioni sullo heap ==

In ogni nodo è presente una coppia ''(k,x)'' in cui ''k'' è il valore della chiave associata alla voce ''x''. Nei dizionari, a differenza delle mappe, ogni chiave può essere associata a più voci (come in un "reale" dizionario ogni parola ha più significati).<br />

Sia '''<math>U'''</math> un insieme di elementi e '''<math>P'''</math> un insieme totalmente ordinato.

Questi tipi di albero hanno la seguente caratteristica: qualsiasi nodo padre ha chiave minore di entrambi (se esistono) i suoi figli.<br />

Un Heap di elementi appartenenti ad '''<math>U'''</math> è un elemento di '''<math>U^*'''</math> che supporta le operazioni di:

In questo modo si garantisce che compiendo un qualsiasi percorso che parte da un nodo ''v'' dell'albero e scendendo nella struttura verso le foglie, si attraversano nodi con chiave sempre maggiore della l'ultima foglia visitata.

- *''Inserimento'': inseriscinello <math> U^* \times U \times Pheap </math>, <math>inserisci (H, e, p)</math>, si inserisce nell'heap H, l'elemento e con priorità <var>p,</var>; dopo l'inserimento l'insiemelo heap mantiene lela proprietà dell'di heap.

*''Rimozione'': nello heap <math>H</math> si rimuove di massima priorità. Dopo la rimozione lo heap mantiene la proprietà di heap

Nell'immagine a fianco è possibile osservare quanto descritto, in aggiunta si può dire che viene definito come ''last'' (ultimo) l'elemento che si trova più a destra nel livello delle foglie. Nell'esempio last ha valore 15. Questo particolare nodo assume un compito determinante nei metodi per la rimozione della chiave minima (che è ovvio supporre, per le proprietà citate, si trovi nella radice) e nell'inserimento di una nuova chiave.

== Definizione ==

Sia '''U''' un insieme di elementi e '''P''' un insieme totalmente ordinato.

Un Heap di elementi appartenenti ad '''U''' è un elemento di '''U*''' che supporta le operazioni di:

- Inserimento: inserisci <math> U^* \times U \times P </math>, <math>inserisci (H, e, p)</math>, inserisce nell'heap H, l'elemento e con priorità p, dopo l'inserimento l'insieme mantiene le proprietà dell'heap.

- Rimozione

- Lettura

== Code di priorità ==

{{Vedi anche|Coda di priorità}}

Un problema classico dell'informatica è ordinare delle code di dati che possiedono una data priorità. Questo tipo di problema viene risolto utilizzando liste concatenate o alberi binari (heap).

Line 43 ⟶ 34:

=== Albero binario con priorità ===

In questo tipo di implementazione ogni nodo contiene sia l'elemento che la priorità dell'elemento. Un albero è '''heap -ordinato''' quando per ogni nodo il valore incontrato nel nodo stesso è maggiore o uguale al valore che si incontra nei figli del suddetto nodo (per maggiori informazioni [[heap sort]]).

<math>\forall v. val(v) \geq val(v')</math>, dove <math>v'</math> è il figlio di v.

Line 52 ⟶ 43:

Questa tipologia di alberi nella programmazione viene sovente implementata attraverso l'utilizzo di [[Vettore (matematica)|vettori]], comprendenti un numero ''N'' di celle (con indici da 0 ad N-1): la prima (indice 0) resta vuota, mentre nella posizione i=1 viene memorizzata la radice. Dato quindi un nodo nella posizione ''i'', gli eventuali figli sono nelle celle ''2i'' (sinistro) e ''2i+1'' (destro).

== Costruzione di un heap binario ==

Nella costruzione di un heap si hanno due tecniche differenti una con un approccio di tipo top-down (ossia si parte dalla radice) e l'altra con un approccio di tipo bottom-up (si parte dal fondo).

Line 67 ⟶ 58:

Si inizia a considerare il primo nodo che non è una foglia si troverà a livello k -1. A questo livello si troveranno <math>2 ^ {k-1}</math> nodi.

Ogni controllo se un nodo contiene un heap ordinato sottostante utilizza 1 confronto tra i due ''fratelli'' e un confronto con il padre per un totale di '''2 confronti'''. A livello k -1 si effettuano <math> 2 * 2 ^ {k -1} = 2 ^ k </math> confronti.

Passando al livello k - 2 si effettuano <math> 2 * 2 ^ {k -2} = 2 ^ {k -1} </math> quindi generalizzando al livello k - i si effettueranno <math>2 * 2 ^ {k -i} = 2 ^ {k - i + 1}</math> ossia

Line 74 ⟶ 65:

== Inserimento di un valore ==

Vediamo ora una rassegna dei principali metodi che sono associati ad una [[coda condi priorità|Priority queue]], ovvero una [[struttura dati]] in cui in ogni momento è possibile associare una priorità alle entry che ne fanno parte.

In primo luogo analizziamo il metodo ''insert'', attraverso il quale, come dice il nome stesso, si inserisce un nuovo nodo all'interno dell'albero:

<pre>

Line 88 ⟶ 79:

</pre>

nell'algoritmo appare una tecnica di scorrimento dell'heap chiamata '''up-heap bubbling''', ovvero, dato un indice ''i'' nell'array, si controlla se le proprietà dell'albero sono verificate per ''<var>i''</var> e per il suo padre, definito come la parte bassa di ''<var>i/2''</var>.

== Sostituzione della radice ==

Capita spesso in una struttura heap, di effettuare la sostituzione della radice con un nuovo elemento.

Una volta che l'elemento viene sostituto capita che l'heap non èsia più ordinato. Per questo motivo si opera il downheap, controllando a livello inferiore (<var>2i</var> e <var>2i+1</var>) quale sia l'elemento più piccolo da promuovere alla posizione di radice. Questa procedura è ricorsiva e permette di riportare l'heap nella condizione di struttura ordinata.

== Cancellazione della radice ==

Un'operazione classica di una struttura heap è la cancellazione della radice. Quest'operazione può comportare problemi a mantenere la struttura dell'heap. Il metodo più semplice è quello di sostituire il valore nella radice che si intende cancellare con il valore minimo presente nell'heap. Inizialmente il valore nella radice dell'heap viene sostituito con l'ultimo valore dell'array associato all'heap che è anche il valore più a destra nell'ultimo livello dell'albero completo. A questo punto si effettua con un approccio di tipo top down il ripristino della struttura dell'heap con una un'operazione di downheap che fa scorrere il valore inserito in radice lungo l'albero binario completo.

== Voci correlate ==

* [[Heap sortHeapsort]]

* [[Heap binomiale]]

== Altri progetti ==

{{Interprogetto|preposizione=sull'}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{strutture dati}}

{{portale|informatica|matematica}}