Heap binomiale
coda di priorità formata da alberi ordinati su heap che hanno come dimensione potenze di due
Un heap binomiale è un insieme di alberi binomiali.
Definizione
Un heap binomiale per essere tale deve soddisfare le seguenti regole:
- per qualsiasi intero k non negativo esiste al più un albero binomiale la cui radice ha grado k (può anche non esserci);
- i nodi all'interno di ogni albero binomiale sono ordinati secondo le regole degli heap (cioè la chiave di un nodo è sempre ≤ alla 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 n chiavi, uno heap binomiale avrà al più log(n) radici, quindi la ricerca del minimo si può eseguire in log(n) passi.
