Heap binomiale: differenze tra le versioni

Versione delle 14:04, 4 feb 2011

Versione delle 14:10, 4 feb 2011

Riga 18:

==Estrazione del nodo con chiave minima==

L'operazione di estrazione del nodo con chiave minima prevede l'eliminazione dallo heap binomiale del nodo con chiave minima restituendone il puntatore. Tale procedura consta di tre fasi e si supponga di indicare con <math>H</math> lo heap binomiale di partenza:

{{...}}

# si cerca la radice con la chiave minima e la si elimina dalla lista delle radici degli alberi binomiali,

# si crea un nuovo heap vuoto <math>H'</math>,

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

==Decremento di una chiave==