Binomiální halda
Author
Albert FloresBinomiální halda je druh haldy, tedy datové struktury, která reprezentuje množinu čísel. Má podobné vlastnosti, jako binární halda, umí však navíc rychlé spojení dvou binomiálních hald.
Binomiální haldy se používají zejména v aplikacích, kde je potřeba provádět rychle operace MIN a MERGE. Učebnicovým příkladem je například Dijkstrův algoritmus. +more Pro zajištění rychlé operace DECREASEKEY (tedy zmenšení prvku reprezentovaného nějakým uzlem) se pak používají Fibonacciho haldy.
Binomiální strom
Binomiální halda je množina binomiálních stromů (na rozdíl od binární haldy, která je sama binárním stromem). Binomiální strom lze definovat rekurzivně:
* Binomiální strom řádu 0 je samostatný vrchol. * Binomiální strom řádu k je kořen, jeho potomci jsou binomiální stromy řádu k-1, k-2, ..., 1, 0.
Binomiální stromy řádu 0 až 3.
Binomiální strom řádu k má 2k uzlů a hloubku k.
Díky své hezké struktuře může být strom řádu k postaven ze dvou stromů řádu k-1 tak, že se jeden strom připojí jako nejlevější potomek ke kořenu druhého stromu (v konstantním čase).
Název binomiální pochází z vlastnosti, že strom řádu k má ve hloubce d právě \tbinom k duzlů.
Struktura binomiální haldy
Binomiální halda bude sloužit k práci s konečnou množinou čísel S (každému uzlu je přiřazen prvek z S). Binomiální halda je množina binomiálních stromů, splňující následující podmínky:
* Každý binomiální strom splňuje haldovou vlastnost - hodnota každého uzlu je větší nebo rovna hodnotě předka. * Pro každý řád je v haldě buď žádný, nebo jeden strom (včetně řádu 0).
První podmínka zajistí, že v kořenu každého stromu je nejmenší prvek.
Druhá podmínka zajistí, že pro uložení n uzlů do haldy stačí vyrobit nejvýše log n + 1 stromů. Počet stromů a jejich řády jsou jednoznačně dány číslem n: každý binomiální strom odpovídá jedničce v binárním zápisu čísla n. +more Například, pro n=13 je binární zápis je 1101. V haldě bude strom řádu 3 (8 uzlů), řádu 2 (4 uzly) a řádu 0 (1 uzel). 8 + 4 + 1 = 13.
Implementace
Žádná z operací nevyžaduje přímý přístup ke stromu řádu k, jednotlivé stromy haldy mohou být uloženy ve spojovém seznamu, vzestupně podle řádu stromu.
Slévání (Merge)
Pro slévání haldy je třeba implementovat slévání dvou stromů řádu k-1 do jednoho stromu řádu k. To provedeme tak, že porovnáme hodnoty kořenů a strom s větší hodnotu připojíme ke kořenu stromu s menší hodnotou (v konstantním čase).
function mergeTree(p, q) if p.root.key
Vkládání (Insert)
Vkládání prvku do haldy je velmi jednoduché. Vytvoří se halda velikosti 1 (1 strom s 1 uzlem) a ta se pak slije s haldou, do které přidáváme. Složitost je O(log n).
Hledání minima
Při hledání minima stačí projít kořeny všech stromů, těch je nejvýše log n. Složitost je O(log n).
Mazání minima
Nejprve najdeme strom s minimem a vyjmeme ho z haldy. Odstraníme kořen stromu a zůstane nám seznam jeho potomků. +more Potomci jsou binomiální stromy různého řádu. Vyrobíme z nich novou haldu a spojíme ji s předchozí haldou. Složitost je O(log n).
Snížení hodnoty uzlu (Decrease key)
Nastavíme uzlu ve stromu novou hodnotu. Dokud je hodnota nižší, než hodnota předka, hodnoty prohodíme (nová hodnota se může dostat až do kořene). Složitost je O(log n).
Mazání uzlu
Nejprve snížíme hodnotu uzlu na záporné nekonečno. Pak použijeme Mazání minima. Složitost je O(log n).
Vyhledání uzlu
Všimněte si, že zde (stejně jako v binární haldě) není možnost efektivního nalezení uzlu. Hledání hodnoty může obnášet průchod všemi uzly všech stromů, tedy složitost je O(n).
Související články
Externí odkazy
Vizualizace [url=https://people. ksp. +moresk/~kuko/gnarley-trees/Binomial. html]binomiální haldy[/url], [url=https://people. ksp. sk/~kuko/gnarley-trees/LazyBinomial. html]lenivé binomiální haldy[/url] a [url=https://people. ksp. sk/~kuko/gnarley-trees/Fibonacci. html]Fibonacciho haldy[/url].