Heap binario: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Nessun oggetto della modifica |
||
Riga 5:
In questo modo si garantisce che compiendo un qualsiasi percorso che parte da un nodo ''v'' dell'albero e scendendo nella struttura verso le foglie, si attraaversano nodi con chiave sempre crescente (in senso lato).
[[Immagine:HeapVector.PNG|300px|left|Implementazione di un heap mediante Vettore]]Questa tipologia di alberi nella programmazione viene sovente implementata attraverso l'utilizzo di [[vettore|vettori]], comprendenti un numero ''N'' di celle (con indici da 0 ad N-1): la prima (indice 0) resta vuota, mentre nella posizione i=1 viene memorizzata la radice. Dato quindi un nodo nella posizione ''i'', gli eventuali figli sono nelle celle ''2i'' (sinistro) e ''2i+1'' (destro).</br>
Nell'immagine a fianco è possibile osservare quanto sopra descritto, in aggiunta si può dire che viene definito come ''last'' l'elemento che si trova più a destra nel livello delle foglie. Nell'esempio last assume il 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.
| |||