Binomická hromada - Binomial heap - Wikipedia

v počítačová věda, a binomická hromada je datová struktura který funguje jako prioritní fronta ale také umožňuje sloučení párů hromád. Je to důležité jako implementace slučitelná hromada abstraktní datový typ (také zvaný tvárná hromada ), což je prioritní fronta podpora operace sloučení. Je implementován jako halda podobný a binární hromada ale pomocí speciální stromové struktury, která se liší od kompletní binární stromy používané binárními hromadami.^[1] Binomické hromady byly vynalezeny v roce 1978 Jean Vuillemin.^[1][2]

Binomická hromada

Binomická halda je implementována jako sada binomický stromy (porovnejte s a binární hromada, který má tvar singlu binární strom ), které jsou definovány rekurzivně takto:^[1]

• Binomický strom řádu 0 je jeden uzel
• Binomický strom řádu ${ displaystyle k}$ má kořenový uzel, jehož děti jsou kořeny binomických stromů řádů ${ displaystyle k-1}$, ${ displaystyle k-2}$, ..., 2, 1, 0 (v tomto pořadí).

Binomické stromy řádu 0 až 3: Každý strom má kořenový uzel s podstromy všech níže uspořádaných binomických stromů, které byly zvýrazněny. Například binomický strom řádu 3 je připojen k binomickému stromu řádu 2, 1 a 0 (zvýrazněn jako modrý, zelený a červený).

Binomický strom řádu ${ displaystyle k}$ má ${ displaystyle 2 ^ {k}}$ uzly a výška ${ displaystyle k}$. Název pochází z tvaru: binomický strom řádu ${ displaystyle k}$ má ${ displaystyle { tbinom {k} {d}}}$ uzly v hloubce ${ displaystyle d}$, a binomický koeficient.Vzhledem ke své struktuře je to binomický strom řádu ${ displaystyle k}$ lze postavit ze dvou stromů řádu ${ displaystyle k-1}$ připojením jednoho z nich jako levého dítěte kořene druhého stromu. Tato funkce je pro spojit provoz binomické hromady, což je jeho hlavní výhoda oproti jiným konvenčním hromadám.^[1][3]

Struktura binomické hromady

Binomická halda je implementována jako sada binomických stromů, které splňují vlastnosti binomické haldy:^[1]

• Každý binomický strom v hromadě se řídí vlastnost minimum-heap: klíč uzlu je větší nebo roven klíči jeho rodiče.
• Může existovat pouze jeden jeden nebo nula binomické stromy pro každou objednávku, včetně nulové objednávky.

První vlastnost zajišťuje, že kořen každého binomického stromu obsahuje nejmenší klíč ve stromu. Z toho vyplývá, že nejmenší klíč v celé haldě je jedním z kořenů.^[1]

Druhá vlastnost znamená, že binomická hromada s ${ displaystyle n}$ uzlů se skládá maximálně z ${ displaystyle 1+ log _ {2} n}$ binomické stromy, kde ${ displaystyle log _ {2}}$ je binární logaritmus. Počet a pořadí těchto stromů je jednoznačně určeno počtem uzlů ${ displaystyle n}$: existuje jeden binomický strom pro každý nenulový bit v souboru binární reprezentace čísla ${ displaystyle n}$. Například desítkové číslo 13 je 1101 v binárním formátu, ${ displaystyle 2 ^ {3} + 2 ^ {2} + 2 ^ {0}}$, a tedy binomická hromada s 13 uzly bude sestávat ze tří binomických stromů řádů 3, 2 a 0 (viz obrázek níže).^[1][3]

Příklad binomické hromady obsahující 13 uzlů s odlišnými klíči.
Hromadu tvoří tři binomické stromy s řády 0, 2 a 3.

Počet různých způsobů, jak ${ displaystyle n}$ položky s odlišnými klávesami mohou být uspořádány do binomické hromady, která se rovná největšímu lichému děliteli ${ displaystyle n!}$. Pro ${ displaystyle n = 1,2,3, tečky}$ tato čísla jsou

1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... (sekvence A049606 v OEIS )

Pokud ${ displaystyle n}$ položky jsou vkládány do binomické hromady v rovnoměrně náhodném pořadí, každé z těchto uspořádání je stejně pravděpodobné.^[3]

Implementace

Protože žádná operace nevyžaduje náhodný přístup ke kořenovým uzlům binomických stromů, mohou být kořeny binomických stromů uloženy v spojový seznam, seřazeno podle vzestupu pořadí stromu. Protože počet podřízených položek pro každý uzel je variabilní, nefunguje dobře, aby každý uzel měl samostatné odkazy na každé ze svých podřízených jednotek, jak by to bylo běžné v binární strom; místo toho je možné implementovat tento strom pomocí odkazů z každého uzlu na jeho dítě nejvyššího řádu ve stromu a na jeho sourozence dalšího menšího řádu než on. Tyto sourozenecké ukazatele lze interpretovat jako další ukazatele v propojeném seznamu podřízených položek každého uzlu, ale s opačným pořadím od propojeného seznamu kořenů: od největšího po nejmenší, spíše než naopak. Tato reprezentace umožňuje propojení dvou stromů stejného řádu, čímž se v konstantním čase vytvoří strom další větší objednávky.^[1][3]

Spojit

Chcete-li sloučit dva binomické stromy stejného řádu, nejprve porovnejte kořenový klíč. Od 7> 3 je černý strom vlevo (s kořenovým uzlem 7) připojen k šedému stromu vpravo (s kořenovým uzlem 3) jako podstrom. Výsledkem je strom řádu 3.

Provoz společnosti slučování ve většině ostatních operací se jako podprogram používají dvě hromady. Základní podprogram v rámci tohoto postupu sloučí páry dvojčlenných stromů stejného řádu. Toho lze dosáhnout porovnáním klíčů v kořenech dvou stromů (nejmenší klíče v obou stromech). Z kořenového uzlu s větším klíčem se vytvoří podřízený kořenový uzel s menším klíčem, čímž se jeho pořadí zvýší o jednu:^[1][3]

funkce mergeTree (p, q) -li p.root.key <= q.root.key vrátit se p.addSubTree (q) jiný        vrátit se q.addSubTree (p)

To ukazuje sloučení dvou binomických hromad. Toho je dosaženo sloučením dvou binomických stromů stejného řádu jeden po druhém. Pokud má výsledný sloučený strom stejné pořadí jako jeden binomický strom v jedné ze dvou hromad, pak jsou tyto dva sloučeny znovu.

Chcete-li sloučit dvě hromady obecněji, seznamy kořenů obou hromád se procházejí současně podobným způsobem jako u slučovací algoritmus, v pořadí od menších řádů stromů po větší řády. Když pouze jedna ze dvou hromad, které jsou sloučeny, obsahuje strom řádu ${ displaystyle j}$, tento strom je přesunut do výstupní haldy. Když obě tyto hromady obsahují strom řádu ${ displaystyle j}$, dva stromy jsou sloučeny do jednoho stromu řádu ${ displaystyle j + 1}$ takže je splněna vlastnost minimum-heap. Později bude nutné sloučit tento strom s nějakým jiným stromem řádu ${ displaystyle j + 1}$ v jedné ze dvou vstupních hromad. V průběhu algoritmu bude zkoumat maximálně tři stromy libovolného řádu, dva ze dvou hromad, které sloučíme, a jeden složený ze dvou menších stromů.^[1][3]

funkce sloučit (p, q) zatímco ne (str. konec () a q.end ()) strom = mergeTree (p.currentTree (), q.currentTree ()) -li ne heap.currentTree (). empty () strom = mergeTree (strom, heap.currentTree ()) heap.addTree (strom) heap.next (); p.next (); q.next ()

Protože každý binomický strom v binomické hromadě odpovídá binárnímu vyjádření své velikosti trochu, existuje analogie mezi sloučením dvou hromad a binárním přidáním velikosti ze dvou hromad, zprava doleva. Kdykoli během sčítání dojde k přenosu, odpovídá to sloučení dvou binomických stromů během sloučení.^[1][3]

Každý strom má maximálně objednávku ${ displaystyle log _ {2} n}$ a proto je doba provozu ${ displaystyle O ( log n)}$.^[1][3]

Vložit

Vkládání nový prvek do haldy lze provést jednoduše vytvořením nové haldy obsahující pouze tento prvek a následným sloučením s původní haldou. Z důvodu sloučení trvá jediné vložení čas ${ displaystyle O ( log n)}$. To však lze zrychlit pomocí procedury sloučení, která zkratky sloučí poté, co dosáhne bodu, kdy pouze jedna ze sloučených hromad má stromy většího řádu. S tímto zrychlením napříč řadou ${ displaystyle k}$ po sobě jdoucích vložení, je celková doba vložení ${ displaystyle O (k + log n)}$. Jiným způsobem, jak to vyjádřit, je to, že (po logaritmické režii pro první vložení do sekvence) každý po sobě vložit má amortizovaný čas z ${ displaystyle O (1)}$ (tj. konstantní) na vložení.^[1][3]

Varianta binomické hromady, zkosit binomickou hromadu, dosáhne konstantní doby vložení nejhoršího případu pomocí lesů, jejichž velikosti stromů jsou založeny na zkosit binární číselný systém spíše než v systému binárních čísel.^[4]

Najděte minimum

Chcete-li najít minimální prvek hromady, najděte minimum mezi kořeny binomických stromů. To lze provést v ${ displaystyle O ( log n)}$ čas, jako jsou právě ${ displaystyle O ( log n)}$ kořeny stromů k prozkoumání.^[1]

Použitím ukazatele na binomický strom, který obsahuje minimální prvek, lze čas pro tuto operaci zkrátit na ${ displaystyle O (1)}$. Ukazatel musí být aktualizován při provádění jakékoli jiné operace než hledání minima. To lze provést v ${ displaystyle O ( log n)}$ čas na aktualizaci, aniž by se zvýšila celková asymptotická doba provozu jakékoli operace.^{[Citace je zapotřebí ]}

Smazat minimum

Na odstranit minimální prvek z haldy nejprve najděte tento prvek, odeberte jej z kořene jeho binomického stromu a získejte seznam jeho podřízených podstromů (které jsou samy o sobě binomickými stromy různých řádů). Transformujte tento seznam podstromů na samostatnou binomickou hromadu jejich uspořádáním od nejmenšího po největší. Poté sloučte tuto hromadu s původní hromadou. Protože každý kořen má nanejvýš ${ displaystyle log _ {2} n}$ děti, vytvoření této nové hromady nějakou dobu trvá ${ displaystyle O ( log n)}$. Sloučení hromád vyžaduje čas ${ displaystyle O ( log n)}$, takže celá minimální operace mazání nějakou dobu trvá ${ displaystyle O ( log n)}$.^[1]

funkce deleteMin (halda) min = heap.trees (). first () pro každého proud v heap.trees () -li current.root pak min = aktuální pro každého strom v min.subTrees () tmp.addTree (strom) halda. odebratTree (min) sloučit (halda, tmp)

Snížit klíč

Po klesající klíč elementu, může se stát menším než klíč jeho rodiče, což porušuje vlastnost minimum-heap. Pokud tomu tak je, vyměňte prvek s jeho nadřazeným prvkem a případně také s jeho prarodičem atd., Dokud již nebude porušena vlastnost minimum-heap. Každý binomický strom má maximálně výšku ${ displaystyle log _ {2} n}$, takže to trvá ${ displaystyle O ( log n)}$ čas.^[1] Tato operace však vyžaduje, aby reprezentace stromu obsahovala ukazatele z každého uzlu na jeho rodiče ve stromu, což trochu komplikuje implementaci dalších operací.^[3]

Vymazat

Na vymazat prvek z haldy, snižte jeho klíč na záporné nekonečno (nebo ekvivalentně na nějakou hodnotu nižší než jakýkoli prvek v haldě) a poté v haldě odstraňte minimum.^[1]

Aplikace

• Diskrétní simulace událostí
• Prioritní fronty

Viz také

• Slabá hromada, kombinace binární haldy a binomické haldy datových struktur

Reference

externí odkazy

• Dvě C implementace binomické hromady (obecný a jeden optimalizovaný pro celočíselné klíče)
• Haskell implementace binomické haldy
• Běžná implementace binomické haldy Lisp