Heap binario: differenze tra le versioni

Versione delle 01:41, 27 mag 2021

Versione delle 01:42, 27 mag 2021

Riga 8:

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.

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

== Definizione ==