Binomiální halda

Binomiální halda je druh haldy, tedy datové struktury, která reprezentuje množinu čísel. Má podobné vlastnosti, jako binární halda, umí však navíc rychlé spojení dvou binomiálních hald.

Binomiální haldy se používají zejména v aplikacích, kde je potřeba provádět rychle operace MIN a MERGE. Učebnicovým příkladem je například Dijkstrův algoritmus. Pro zajištění rychlé operace DECREASEKEY (tedy zmenšení prvku reprezentovaného nějakým uzlem) se pak používají Fibonacciho haldy.

Binomiální strom

Binomiální halda je množina binomiálních stromů (na rozdíl od binární haldy, která je sama binárním stromem). Binomiální strom lze definovat rekurzivně:

• Binomiální strom řádu 0 je samostatný vrchol.
• Binomiální strom řádu k je kořen, jeho potomci jsou binomiální stromy řádu k-1, k-2, ..., 1, 0.

Binomiální stromy řádu 0 až 3.

Binomiální strom řádu k má 2^k uzlů a hloubku k.

Díky své hezké struktuře může být strom řádu k postaven ze dvou stromů řádu k-1 tak, že se jeden strom připojí jako nejlevější potomek ke kořenu druhého stromu (v konstantním čase).

Název binomiální pochází z vlastnosti, že strom řádu k má ve hloubce d právě ${\tbinom {k}{d}}$uzlů.

Struktura binomiální haldy

Binomiální halda bude sloužit k práci s konečnou množinou čísel S (každému uzlu je přiřazen prvek z S). Binomiální halda je množina binomiálních stromů, splňující následující podmínky:

• Každý binomiální strom splňuje haldovou vlastnost - hodnota každého uzlu je větší nebo rovna hodnotě předka.
• Pro každý řád je v haldě buď žádný, nebo jeden strom (včetně řádu 0).

První podmínka zajistí, že v kořenu každého stromu je nejmenší prvek.

Druhá podmínka zajistí, že pro uložení n uzlů do haldy stačí vyrobit nejvýše log n + 1 stromů. Počet stromů a jejich řády jsou jednoznačně dány číslem n: každý binomiální strom odpovídá jedničce v binárním zápisu čísla n. Například, pro n=13 je binární zápis je 1101. V haldě bude strom řádu 3 (8 uzlů), řádu 2 (4 uzly) a řádu 0 (1 uzel). 8 + 4 + 1 = 13.

Implementace

Žádná z operací nevyžaduje přímý přístup ke stromu řádu k, jednotlivé stromy haldy mohou být uloženy ve spojovém seznamu, vzestupně podle řádu stromu.

Slévání (Merge)

Pro slévání haldy je třeba implementovat slévání dvou stromů řádu k-1 do jednoho stromu řádu k. To provedeme tak, že porovnáme hodnoty kořenů a strom s větší hodnotu připojíme ke kořenu stromu s menší hodnotou (v konstantním čase).

function mergeTree(p, q)
    if p.root.key <= q.root.key
        return p.addSubTree(q)
    else
        return q.addSubTree(p)

Slévání dvou hald je nejzajímavější operace a je použita při provádění dalších operací.

Seznamy kořenů dvou hald se prochází najednou (vzestupně podle řádu stromů). Pokud pouze jedna z hald má strom řádu k, tento strom se přesune do výsledku. Pokud obě haldy mají strom řádu k, oba tyto stromy se spojí do stromu řádu k+1. Ten bude třeba přidat do výsledku v příštím kroku.

Jelikož každý strom binomiální haldy odpovídá bitu v binárním zápisu, na slévání hald lze nahlížet jako na sčítání čísel (velikostí obou hald). Kdykoli při sčítání nastane posun do vyššího řádu, odpovídá to spojení dvou binomiálních stromů během slévání hald.

Jelikož halda má nejvýše log n stromů, stromy se spojují v konstantním čase, slévání hald má složitost O(log n).

function merge(p, q)
    while not (p.end() and q.end())
        tree = mergeTree(p.currentTree(), q.currentTree())
        
        if not heap.currentTree().empty()
            tree = mergeTree(tree, heap.currentTree())
        
        heap.addTree(tree)
        heap.next(); p.next(); q.next()

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. Složitost je O(log n).

Hledání minima

Při hledání minima stačí projít kořeny všech stromů, těch je nejvýše log n. Složitost je O(log n).

Mazání minima

Nejprve najdeme strom s minimem a vyjmeme ho z haldy. Odstraníme kořen stromu a zůstane nám seznam jeho potomků. Potomci jsou binomiální stromy různého řádu. Vyrobíme z nich novou haldu a spojíme ji s předchozí haldou. Složitost je O(log n).

Snížení hodnoty uzlu (Decrease key)

Nastavíme uzlu ve stromu novou hodnotu. Dokud je hodnota nižší, než hodnota předka, hodnoty prohodíme (nová hodnota se může dostat až do kořene). Složitost je O(log n).

Mazání uzlu

Nejprve snížíme hodnotu uzlu na záporné nekonečno. Pak použijeme Mazání minima. Složitost je O(log n).

Vyhledání uzlu

Všimněte si, že zde (stejně jako v binární haldě) není možnost efektivního nalezení uzlu. Hledání hodnoty může obnášet průchod všemi uzly všech stromů, tedy složitost je O(n).

Související články

• Fibonacciho halda

Externí odkazy

• Obrázky, zvuky či videa k tématu Binomiální halda na Wikimedia Commons
• Vizualizace binomiální haldy, lenivé binomiální haldy a Fibonacciho haldy