Heap binario: differenze tra le versioni

Versione delle 11:16, 29 giu 2021

Versione delle 11:20, 29 giu 2021

Riga 6:

== Implementazione con array ==

Dato ''<var>j''</var>, indice ad un nodo della heap, si ha che:

* il padre di ''<var>j''</var> è il nodo in posizione <math>j/2</math>

* il figlio sinistro di ''<var>j''</var> è il nodo in posizione <math>j*2*j</math>

* il figlio destro di ''<var>j''</var> è il nodo in posizione <math>j*2*j+1</math>

Si possono quindi definire le funzioni <samp>Padre(j)</samp>, <samp>FiglioSX(j)</samp>, <samp>FiglioDX(j)</samp> che rispettivamente restituiscono l'indice del padre, del figlio sinistro e del figlio destro di <var>j</var>. 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.