Un heap binomiale è un insieme di alberi binomiali che soddisfa le seguenti proprietà:
Gli heap binomiali appartengono alla classe di strutture dati definite come heap aggregabili ossia strutture dati di tipo heap che oltre alle consuete procedure di ricerca della chiave minima, inserimento di un nodo, estrazione del nodo con chiave minima ed eliminazione di una chiave (operazioni implementate ad esempio negli heap binari), consentono anche l'implementazione dell'operazione di unione fra due heap che, a partire da due heap iniziali, restituisce un unico heap il cui insieme delle chiavi è pari all'unione degli insiemi delle chiavi dei due heap di partenza.
La procedura di creazione restituisce uno heap binomiale vuoto e richiede tempo di esecuzione . Il puntatore head[H] punterà alla testa della lista delle radici dello heap.
Make-Heap() crea H ed assegna ad esso spazio di memoria head[H] ← NIL return H
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ù dunque il tempo per l'esecuzione della ricerca è .
Dato che un albero binomiale, per sua definizione, contiene esattamente nodi al suo interno, con 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 in posizione indica la presenza di un albero di grado all'interno della struttura. Lo heap binomiale risultante avrà di conseguenza la stessa struttura del numero decimale risultato della somma.
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
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.
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 ) e in una successiva operazione di unione dello heap binomiale originale con lo heap binomiale appena creato (operazione che richiede tempo di esecuzione ). Il tempo complessivo di esecuzione è pertanto .
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 lo heap binomiale di partenza:
La procedura impiega tempo di esecuzione .
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 , il puntatore al nodo da modificare e la nuova chiave da inserire in , la procedura consta di 3 fasi:
La procedura impiega tempo di esecuzione .
L'operazione di eliminazione di una chiave (senza che ne venga restituito un puntatore) consiste in due fasi:
Le due operazioni richiedono rispettivamente tempo di esecuzione pertanto il tempo di esecuzione complessivo è sempre .