Články » Programování » Algoritmizace

Binomiální halda

Vydáno dne v kategorii Algoritmizace; Autor: ; Počet přečtení: 6 525

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 (k ≤ 0) je:

  • pro k = 0 jeden uzel
  • pro k větší nule je uspořádaný strom tvořený spojenou dvojicí stromů .

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 uzlů.
  • V hloubce i je 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ů mohou nastat dvě situace. Když , mohu stromy sloučit do jednoho stromu stupně . Kořenem výsledného stromu bude ten ze stromů s menším kořenem.

Pokud ale , 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 , tak sloučením dvou stromů stupně 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 = 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 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 (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.


Tento clanek pro vas napsal Jakub Vojacek!

Test

Určete intervaly monotónnosti funkce


Hlavolam

Máte 10 pytlů zlaťáků. Jeden z Vašich sluhů, kteří měli na starost přepravu peněz, Vás chtěl okrást, a v jednom z pytlů z každé mince, která normálně váží 10 gramů, 1g zlata upiloval. Máte digitální váhy (dáte na ně předmět a oni ukáží, jakou má hmotnost). Dokážete na jedno vážení určit, který pytel obsahuje lehčí mince a tedy, kterého sluhu máte vyhodit?