Heap binomiale

Un heap binomiale è un insieme di [[Albero binomiale|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),
2. i nodi all'interno di ogni albero binomiale sono ordinati secondo le regole degli heap (cioè la chiave di un nodo è sempre minore o uguale della chiave dei suoi figli).

Ricerca del minimo

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.

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