Heap binario: differenze tra le versioni

Versione delle 01:34, 14 mag 2006

Versione delle 18:18, 6 giu 2006

Riga 1:

[[Immagine:HeapVector.PNG|300px|right|Implementazione di un heap mediante Vettore]]

Un '''heap''' è una [[struttura dati]] utilizzata in informatica, più precisamente un [[albero binario]] quasi completo usato principalmente per la memorizzazione di collezioni di dati, dette [[Dizionario|dizionari]].

Riga 5 ⟶ 6:

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]]</br></br>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.

</br>

Vediamo ora una rassegna dei principali metodi che sono associati ad una [[coda con priorita'|Priority queue]], ovvero una struttura dati in cui in ogni momento e' possibile associare una priorita' alle entry che ne fanno parte.

In primo luogo analizziamo il metodo ''insert'', attraverso il quale, come dice il nome stesso, si inserisce un nuovo nodo all'interno dell'albero: </br>

</br></br></br></br></br>

<pre>

insert (k, x)