Heap binario: differenze tra le versioni

Versione delle 19:24, 6 nov 2015

Versione delle 20:52, 10 nov 2015

Riga 3:

{{Avvisounicode}}

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

Un '''heap binario''', è unaun [[struttura datiheap]] utilizzatasviluppato insu un [[informaticaalbero binario]], più precisamente un vettore o una lista che soddisfi la proprietà heap. Un heap binario può essere visto, per comodità di rappresentazione, come un [[albero binario]] quasi completo. È usato principalmente per la raccolta di collezioni di dati, dette dizionari, e per la rappresentazione di [[code di priorità]].

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.

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.

Dato ''j'', indice ad un nodo della heap, si definiscono '''Padrepadre di j''j'' il nodo in posizione <math>j/2</math>, '''Figliofiglio sinistro di j''j'' il nodo in posizione <math>j*2</math> e '''Figliofiglio destro di j''j'' il nodo in posizione <math>j*2+1</math>. 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.

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

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

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

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

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 />

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

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.

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.

Line 22 ⟶ 12:

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

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

- *Lettura

- Rimozione

- Lettura

== Code di priorità ==

Line 51 ⟶ 38:

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