Heap binario: differenze tra le versioni

Versione delle 01:56, 27 mag 2021

Versione delle 01:58, 27 mag 2021

Riga 6:

===Implementazione con array===

Dato ''j'', indice ad un nodo della heap, si definisconoha che:
* il padre di ''j'' è il nodo in posizione <math>j/2</math>,
* il figlio sinistro di ''j'' è il nodo in posizione <math>j*2</math>
* eil 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.

Nell'immagine in alto a destra è 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.