Heap binomiale: differenze tra le versioni

Versione delle 19:24, 6 nov 2015

Versione delle 22:47, 15 nov 2016

Riga 57:

== Decremento di una chiave ==

L'operazione di decremento di una chiave consiste nel sovrascrivere il valore del nodo con un nuovo valore strettamente minore. Quindi, dato un heap binomiale <math>H</math>, il puntatore <math>x</math> al nodo da modificare e la nuova chiave <math>k</math> da inserire in <math>x</math>, la procedura consta di 3 fasi:

{{...}}

# si verifica che il valore <math>k</math> sia strettamente minore del valore della chiave attualmente presente nel nodo <math>x</math>,

# 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)</math>.

== Eliminazione di una chiave ==