Definujte binomiální strom a binomiální minimovou haldu. Popište operaci odebrání minimálního prvku z binomiální minimové haldy (BHExtractMin) a její časovou složitost.
BH je definována v předchozí Veta otázce
BH se skládá ze seřazené posloupnosti binomiálních stromů unikátního řádu
→ definice binomálního stromu říká, že kořen tohoto stromu bude globálně nejmenší prvek tohoto stromu
Musíme tedy prozkoumat všechny stromy T1,…,Tn , které tvoří danou BH a zjistit nejmenší ze všech jejich kořenů
→ časová složitost O(log n)
Tento strom následně odpojíme z BH a z kořene tohoto binomálního stromu následně odebereme klíč a tento vrchol stromu Ti smažeme
→ tím nám vznikne(Ti) nových stromů s unikátními řády, toto seskupení můžeme považovat za novou BH2
Provedeme tedy operaci slití dvou BH - BHMerge(BH1,BH2) - výsledek této operace je původní BH s odstraněným minimem