Heap binomiale

Un heap binomiale è un insieme di alberi binomiali che soddisfa le seguenti proprietà:

1. per qualsiasi intero ${\displaystyle k}$ non negativo esiste al più un albero binomiale la cui radice ha grado ${\displaystyle k}$ (può anche non esserci). Ciò significa anche che non possono esservi più di un albero binomiale con il medesimo grado,
2. ogni albero binomiale gode della proprietà di ordinamento parziale degli heap, ossia ogni nodo di ciascun albero è tale che la propria chiave sia sempre maggiore o uguale della chiave del nodo padre.

Creazione di uno heap binomiale

La procedura di creazione restituisce uno heap binomiale vuoto e richiede tempo di esecuzione ${\displaystyle \Theta (1)}$ .

Ricerca della chiave minima

Essendo lo heap binomiale rappresentabile come una lista concatenata di alberi binomiali e tenendo conto che ogni albero binomiale ha come radice la sua chiave minima si può facilmente intuire che dato un insieme di ${\displaystyle n}$  chiavi, uno heap binomiale avrà al più ${\displaystyle lg(n)}$  radici, quindi la ricerca del minimo si può eseguire in ${\displaystyle lg(n)}$  passi.

Unione di due heap binomiali

Inserimento di un nodo

Estrazione del nodo con chiave minima

Decremento di una chiave

Eliminazione di una chiave

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica