Heap binario: differenze tra le versioni

Versione delle 20:52, 10 nov 2015

Versione delle 21:14, 10 nov 2015

Riga 3:

{{Avvisounicode}}

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

Un '''heap binario''', è un [[heap]] sviluppato su un [[albero binario]]. 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à]]. L'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.

*Condizione di forma: tutti i livelli dell'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.

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