Heap binomiale: differenze tra le versioni

Versione delle 06:03, 20 mag 2013

Versione delle 19:43, 22 lug 2013

Riga 25:

==Unione di due heap binomiali==

Dato che un albero binomiale, per sua definizione, contiene esattamente <math>2^k</math> nodi al suo interno, con <math>k</math> grado dell'albero, deduciamo che uno heap binomiale possa contenere un qualsiasi numero di nodi al suo interno, componendo alberi binomiali di gradi diversi, esattamente come una cifra binaria è espressa in funzione delle diverse potenze di 2.

{{...}}

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

Per ogni albero x della lista:

next <- next[x];

sibling <- next[next];

if(rank[x] == rank[next])

if(rank[next] == rank[sibling])

merge(next, sibling);

else

merge(x, next);

x <- next;

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.

==Inserimento di un nodo==