Definujte binomiální strom a binomiální minimovou haldu. Popište operaci sloučení dvou binomiálních hald (BHMerge) a vložení prvku do binomiální haldy a jejich časovou složitost.

Binomiální strom

Binomiální strom řádu k (značíme Bk) je uspořádaný (t.j. zaleží na pořadí synů) zakořeněný strom, pro který platí:

1. B0 je tvořen pouze kořenem
2. Pro k ≥ 1 získáme Bk ze stromů B0, B1,…,Bk-1 tak, že přidáme nový kořen a kořeny těchto stromů (vzestupně) přidáme jako potomky nového kořene

Alternativní definice

Binomiální strom řádu k (značíme Bk) je uspořádaný (t.j. zaleží na pořadí synů) zakořeněný strom, pro který platí:

1. B0 je tvořen pouze kořenem
2. Pro k ≥ 1 se Bk skládá ze stromu Bk-1, pod jehož kořenem je jako nejpravější syn Bk-1

Ekvivalence definic