Binomiální halda

Binární halda nepodporuje žádnou efektivní metodu pro slučování dvou hald. Proto existují další typy hald, které podporují slučování se složitostí O(log(n)). Jsou to binomické a Fibonacciho haldy.

Většinu z operací nad binomiálními haldami si můžete vyzkoušet na java appletu.

Binomiální strom

Každý uzel v binomiálním stromu má stejnou nebo větší hodnotu než jeho rodič. Nejmenší uzel tedy bude kořenem stromu.

Binomiální strom `B_k` (k ≤ 0) je:

• pro k = 0 jeden uzel
• pro k větší nule je `B_k` uspořádaný strom tvořený spojenou dvojicí stromů `B_{k-1}`.

Pro k = 1 bude strom tvořen dvě dvojicí stromů k = 0:

Pro k = 2 bude strom tvořen dvojicí stromů k = 1, přičemž druhý strom bude připojen do kořene prvního stromu.

Obecně platí následující obrázek:

Pro binomiální strom platí:

• Výška stromu `B_k` je k.
• Strom `B_k` má `2^k` uzlů.
• V hloubce i je `k \choose i` uzlů

Binomiální halda

Binomiální halda je množina binomiálních stromů uspořádán podle stupně stromu k. Binomiální halda stupně k bude mít vždy právě jeden strom stupně k. Pokud by stromů stupně k bylo více, mohly by se tyto stromy spojit a stupeň haldy by tedy byl k+1.

Pro binomiální haldu o n uzlech je halda tvořena maximálně log(n)+1 stromy. Počet stromů a jejich stupeň je reprezentován v binární reprezentaci čísla n. Například pro n = 14 = 11102 = 23+22+21 bude jeden strom třetího, druhého a první stupně a nebude žádný strom nultého stupně.

Sloučení hald

Při slučování dvou binomiálních stromů `B_k,\ B_l` mohou nastat dvě situace. Když `k=l`, mohu stromy sloučit do jednoho stromu stupně `k+1`. Kořenem výsledného stromu bude ten ze stromů s menším kořenem.

Pokud ale `k\neq l`, tak stromy nemohu sloučit a vznikne binomiální halda.

Při slučování hald budeme postupovat podobně, akorát si musíme dát pozor na to, že strom stupně `k` nepůjde s sloučit s žádným jiným stromem `l,\ l=k`, tak sloučením dvou stromů stupně `k-1` vznikne strom stupně `k`, který už půjde sloučit s původním stromem.

Celé se to dá srovnat s binárním sčítáním:

31 = 111112
13 = 11012
 11111
 +1101
-------
101100

Každý přenos v binárním sčítáním odpovídá sloučení dvou stromů. V tomto případě tedy došlo ke sloučení 4 stromů.

Vložení nového prvku

Vkládání nového prvku není nic jiného, než slučování původní haldy s haldou tvořené pouze vkládaným prvkem.

Nalezení minima

Jelikož minimální prvek binomiálního stromu, tak minimální prvek binomiální haldy bude ten nejmenší z množiny kořenů stromů.

Odstranění minima

Abychom odstranili minimum, nejprve ho musíme najít. Jelikož je to kořen, tak po něm zbude `k \choose 1` podstromů. Tyto podstromy vložíme do nové haldy a tu sloučíme s haldou původní.

Zmenšení hodnoty prvku

Snížením hodnoty nějakého prvku můžeme porušit pravidlo binomiálního stromu (každý uzel je stejně velký nebo větší než jeho rodič) a proto může být třeba prohodit změněný prvek s jeho rodičem (toto je možné provádět i vícekrát, prvek se může dostat až do kořene stromu).

Odstranění prvku z haldy

Pro odstranění prvku z haldy nejprve musíme zmenšit hodnotu daného prvku na `-\infty` (nebo nejmenší možnou hodnotu -1). Prvek tak probublá až do kořene stromu a poté stačí odstranit nejmenší prvek.

Složitosti operací

Implementace binomiální haldy

Implementace v jazyce Python a C.