Binomiální halda

Vydáno dne v kategorii Algoritmizace; Autor: Jakub Vojáček; Počet přečtení: 12 295

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í halda

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:

Binomiální halda

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.

Binomiální halda

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

Binomiální halda

Pro binomiální strom platí:

  • Výška stromu B_k je k.
  • Strom B_k2^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ě.

Binomiální halda

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.

Binomiální halda

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

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ů.

Binomiální halda

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í

OperaceSlož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.

Test

Vypočítejte \lim\limits_{x\to\infty}\left(\frac{x^3}{2x^2-1}-\frac{x^2}{2x+1}\right)


Hlavolam

Loď plave v jezeře a na její palubě je kámen. Co se stane s hladinou jezera, pokud kámen hodíme přes palubu do vody?