Binomiální halda je druh haldy, tedy datové struktury, která reprezentuje množinu čísel. Binomiální haldy se používají zejména v aplikacích, kde je potřeba provádět rychle operace MIN a MERGE.
Definice
Binomiální halda je uspořádaná množina binomiálních stromů T = T1, … , Tl, kde platí:
- Stromy Ti jsou v T uspořádány vzestupně podle svých řádů.
- n=|V(T1)|+ … +|V(Tl)|.
- Pro každé nezáporné k se v množině T vyskytuje nejvýše jeden binomiální strom řádu k.
- Každý vrcholv v každém stromu obsahuje klíč k(v).
- Pro každý strom Ti platí haldové uspořádání klíčů, čili ∀ v ∈ V(Ti) a ∀ jeho syny sj, j = 1, , . . . , m, platí k(v) ≤ k(sj).
Vlastnosti
Binomiální strom řádu k má 2k uzlů a hloubku k.
Operace
| Operace | Popis | Složitost |
|---|---|---|
| Insert | Vloží nový prvek | O(log n), Amort.Θ(1) |
| FindMin/FindMax | Vrátí minimum/maximum | O(1) |
| ExtractMin/ExtractMax | Odstraní minimální/maximální prvek | O(log n) |
| Delete | Vymaže prvek z BH | O(log n) |
| Merge | Sloučí dvě BH do jedné | O(log n) |
| Build | Vytvoří BH z n prvků | O(n) |
| Decrease Key | Sníží hodnotu klíče prvku | O(log n) |
| Decrease Key | Zvýší hodnotu klíče prvku | O(log n) |
Vkládání (Insert)
Vkládání prvku do haldy je velmi jednoduché. Vytvoří se halda velikosti 1 (1 strom s 1 uzlem) a ta se pak slije s haldou, do které přidáváme.
Implementace
Pro uložení uspořádané množiny stromů T se používá spojový seznam.