Heap binario: differenze tra le versioni

Versione delle 02:44, 21 giu 2007

Versione delle 14:54, 14 lug 2007

Riga 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 attraversano nodi con chiave sempre crescente (in senso lato).

Questa tipologia di alberi nella programmazione viene sovente implementata attraverso l'utilizzo di [[Vettore (matematica)|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>

== Code con priorità ==

Un problema classico dell'informatica è ordinare delle code di dati che possiedono una data priorità. Questo tipo di problema viene risolto utilizzato liste concatenate o alberi binari (heap).

=== Lista concatenata con priorità ===

Nell'implementazione attraverso liste concatenate, si ha in input un insieme di elementi (in quanto non è definita una relazione d'ordine dell'elemento ma è una proprietà intrinseca della sua priorità), e si otterrà una lista. Ad esempio se in input si ha

<math> C = \{12,7,2,8,3 \} </math> si otterrà una lista del tipo:

[[Immagine:lista_head_priorita.gif]]

La posizione nella lista non è indicativa, ma lo è la priorità di ogni singolo elemento. Il costo della gestione della lista concatenata è troppo alto per questo motivo si opta per la soluzione tramite albero binario.

=== Albero binario con priorità ===

In questo tipo di implementazione ogni nodo contiene sia l'elemento che la priorità dell'elemento. Un albero è '''heap ordinato''' quando per ogni nodo il valore incontrato nel nodo stesso è maggiore o uguale al valore che si incontra nei figli del suddetto nodo (per maggiori informazioni [[heap sort]]).

<math>\forall v </math><math>val(v) \geq val(v^')</math> dove <math>v^'</math> è il figlio di v.

Se un albero è heap ordinato, la radice contiene l'elemento con valore maggiore.

==== Albero binario head ordinato completo ====

E' un albero binario, heap ordinato, in cui tutti i livelli sono saturi, tranne che l'ultimo che risulta completo da sinistra verso destra.

Questa tipologia di alberi nella programmazione viene sovente implementata attraverso l'utilizzo di [[Vettore (matematica)|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>

== Costruzione di un heap ==

Nella costruzione di un heap si hanno due tecniche top-down (ossia si parte dalla radice) o bottom-up si parte dal fondo.

=== Rappresentazione top-down ===

Avendo in input il seguente vettore di partenza bisogna costruire un albero binario heap ordinato

<math> v = \{3,7,4,9,2,5,1,10,8\}</math>

[[Immagine:heap_top_down.gif]]

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 è 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: