Heap binario: differenze tra le versioni

Versione delle 11:22, 29 giu 2021

Versione delle 11:24, 29 giu 2021

Riga 33:

=== 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. val(v) \geq val(v')</math>, dove <math>v'</math> è il figlio di v.

Riga 57:

Si inizia a considerare il primo nodo che non è una foglia si troverà a livello k -1. A questo livello si troveranno <math>2 ^ {k-1}</math> nodi.

Ogni controllo se un nodo contiene un heap ordinato sottostante utilizza 1 confronto tra i due ''fratelli'' e un confronto con il padre per un totale di '''2 confronti'''. A livello k -1 si effettuano <math> 2 * 2 ^ {k -1} = 2 ^ k </math> confronti.

Passando al livello k - 2 si effettuano <math> 2 * 2 ^ {k -2} = 2 ^ {k -1} </math> quindi generalizzando al livello k - i si effettueranno <math>2 * 2 ^ {k -i} = 2 ^ {k - i + 1}</math> ossia

Riga 78:

</pre>

nell'algoritmo appare una tecnica di scorrimento dell'heap chiamata '''up-heap bubbling''', ovvero, dato un indice ''i'' nell'array, si controlla se le proprietà dell'albero sono verificate per ''<var>i''</var> e per il suo padre, definito come la parte bassa di ''<var>i/2''</var>.

== Sostituzione della radice ==

Capita spesso in una struttura heap, di effettuare la sostituzione della radice con un nuovo elemento.

Una volta che l'elemento viene sostituto capita che l'heap non sia più ordinato. Per questo motivo si opera il downheap, controllando a livello inferiore (<var>2i</var> e <var>2i+1</var>) quale sia l'elemento più piccolo da promuovere alla posizione di radice. Questa procedura è ricorsiva e permette di riportare l'heap nella condizione di struttura ordinata.

== Cancellazione della radice ==