Heap Binomiali

Definizione

Uno Heap Binomiale H è una foresta di Alberi Binomiali tale che:

• Ciascun albero binomiale in H gode della proprietà di min-heap;
• Per ogni , H contiene al più un solo albero binomiale di grado k.

Maggiorazione Grado Massimo di un Nodo

Conseguenze immediate della definizione:

• In ciascun albero binomiale in un heap binomiale, la radice contiene la chiave minima dell’albero;
• Uno heap binomiale H con n nodi è formato al più da alberi binomiali.
• Infatti, sia l’albero binomiale di grado massimo in H, si ha , da cui , e quindi .
• Pertanto il numero di alberi binomiali in H è al più