Heap binario: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m la lingua italiana non prevede elisione nell'articolo determinativo prima di una consonante. In inglese la h e' una consonante non muta, quindi si scrive "Lo heap" come nel celebre titolo "Lo Hobbit" |
mNessun oggetto della modifica |
||
Riga 3:
Uno '''heap binario''', è uno [[Heap (struttura dati)|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
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.
| |||