Binomiální halda

Technology

12 hours ago

Author

Binomiá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.

Important

Fibonacciho halda

halda (datová struktura)

datová struktura

Dijkstrův algoritmus

Soubor:Binomial Trees.svg

Spojový seznam

Kategorie:Haldy

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