Heap binomiale: differenze tra le versioni

Versione delle 11:54, 15 gen 2019

Versione delle 12:09, 30 nov 2020

Riga 18:

== Ricerca della chiave minima ==

Ogni albero binomiale che costituisce uno heap binomiale gode della proprietà di ordinamento parziale degli heap, pertanto ognuno di essi avrà la chiave minima in corrispondenza della radice. La chiave minima dello heap binomiale sarà, quindi, contenuta, in uno dei nodi radice dei vari alberi binomiali che lo costituiscono, di conseguenza la ricerca della chiave minima si riduce ad una ricerca del minimo nella lista delle radici degli alberi binomiali. Il numero massimo di radici di alberi binomiali di uno heap binomiale è al più <math>\lfloor lgn\log n \rfloor +1</math> dunque il tempo per l'esecuzione della ricerca è <math>O(lgn\log n)</math>.

== Unione di due heap binomiali ==

Riga 43:

== Inserimento di un nodo ==

L'operazione di inserimento di un nodo in uno heap binomiale consiste nella creazione di un nuovo heap binomiale costituito solo dal nodo da inserire (con tempo di esecuzione <math>O(1)</math>) e in una successiva operazione di unione dello heap binomiale originale con lo heap binomiale appena creato (operazione che richiede tempo di esecuzione <math>O(lgn\log n)</math>). Il tempo complessivo di esecuzione è pertanto <math>O(lgn\log n)</math>.

== Estrazione del nodo con chiave minima ==

Riga 51:

# si inverte la lista dei figli della radice precedentemente eliminata e si considera come testa della nuova lista delle radici il puntatore al primo nodo ottenuto,

# si effettua, infine, l'operazione di unione tra gli heap <math>H</math> e <math>H'</math>.

La procedura impiega tempo di esecuzione <math>O(lgn\log n)</math>.

== Decremento di una chiave ==

Riga 58:

# si sovrascrive il valore della chiave del nodo <math>x</math> con il valore <math>k</math>,

# utilizzando due puntatori <math>y</math> e <math>z</math> che inizialmente puntano al nodo <math>x</math> e al nodo padre di <math>x</math>, si verifica se la chiave del nodo <math>x</math> è minore della chiave del nodo <math>z</math> e in tal caso si scambiano le chiavi dei due nodi. Dopo lo scambio i puntatori <math>y</math> e <math>z</math> vengono aggiornati e punteranno rispettivamente al vecchio nodo puntato da <math>z</math> e al nodo padre di <math>z</math>. Questa fase viene ripetuta fino a quando la condizione di disuguaglianza delle chiavi non viene più soddisfatta o fino a quando <math>z</math> punta ad una locazione di memoria nulla.

La procedura impiega tempo di esecuzione <math>O(lgn\log n)</math>.

== Eliminazione di una chiave ==

Riga 64:

# si decrementa al minimo valore rappresentabile dal calcolare il valore della chiave da eliminare,

# si estrae la chiave con valore minimo dallo heap binomiale.

Le due operazioni richiedono rispettivamente tempo di esecuzione <math>O(lgn\log n)</math> pertanto il tempo di esecuzione complessivo è sempre <math>O(lgn\log n)</math>.

== Bibliografia ==