Heap binario: differenze tra le versioni

Versione delle 18:39, 19 nov 2015

Versione delle 13:17, 6 gen 2016

Riga 5:

Un '''heap binario''', è un [[heap]] sviluppato su un [[albero binario]]. È 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—per convenzione—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.