Binomiální halda

Vydáno dne 17. 11. 2011 v kategorii Algoritmizace; Autor: Jakub Vojáček; Počet přečtení: 12 311

Binomiální halda podporuje rychlé vkládání prvků a hlavně rychlé slučování dvou hald.

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 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 je k.
Strom má 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 = 1110₂ = 2³+2²+2¹ 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ě 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ě , 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 = 11111₂
13 = 1101₂
 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í

Operace	Složitost
Sloučení hald	`Ο(log(n))`
Vložení nového prvku	`Ο(log(n))`
Nalezení minima	`Ο(log(n))`
Odstranění minima	`Ο(log(n))`
Zmenšení hodnoty prvku	`Ο(log(n))`
Odstranění prvku z haldy	`Ο(log(n))`

Implementace binomiální haldy

Implementace v jazyce Python a C.

Binomiální halda

Binomiální strom

Binomiální halda

Sloučení hald

Vložení nového prvku

Nalezení minima

Odstranění minima

Zmenšení hodnoty prvku

Odstranění prvku z haldy

Složitosti operací

Implementace binomiální haldy

Test

Hlavolam