Heap binomiale: differenze tra le versioni

Versione delle 11:02, 24 apr 2018

Versione delle 16:19, 4 mag 2018

Riga 12:

La procedura di creazione restituisce uno heap binomiale vuoto e richiede tempo di esecuzione <math>\Theta(1)</math>. Il puntatore ''head[H]'' punterà alla testa della lista delle radici dello heap.

<code>

Make-Heap()

crea H ed assegna ad esso spazio di memoria

head[H] ← NIL

return H

</code>

== Ricerca della chiave minima ==

Line 26 ⟶ 24:

La somma di due heap binomiali avviene esattamente come la somma tra due numeri binari, dove un <math>1</math> in posizione <math>k</math> indica la presenza di un albero di grado <math>k</math> all'interno della struttura. Lo heap binomiale risultante avrà di conseguenza la stessa struttura del numero decimale risultato della somma.

<code>

Union(H1, H2)

Creo una nuova lista contenente tutti gli alberi binomiali di H1 e H2 ordinati per grado

Line 41 ⟶ 38:

Merge(H1, H2)

Pongo H2 come figlio della radice di H1

</code>

L'algoritmo di unione crea un'unica lista dinamica contenente tutti gli alberi binomiali ordinati per grado crescente.

Dopodiché scorre ogni elemento (che sarà la radice di un albero binomiale) osservando i suoi due elementi successivi.