1. Binomiální haldy V této kapitole popíšeme datovou strukturu zvanou binomiální halda. Základní funkcionalita binomiální haldy je podobná binární haldě, nicméně jí dosahuje jinými metodami a navíc podporuje funkci BHMerge, která umí rychle sloučit dvě binomiální haldy do jedné. Shrňme na začátek podporované operace spolu s jejich časy. Číslo N udává počet prvků v haldě a haldu zde chápeme jako minimovou. Operace
Čas
Komentář ∗
BHInsert Θ(log N ), Θ (1) Vloží nový prvek. BHGetMin Θ(1) Vrátí minimum množiny. BHExtractMin Θ(log N ) Vrátí a odstraní minimum množiny. BHMerge Θ(log N ) Sloučí dvě haldy do jedné. BHBuild Θ(N ) Postaví z N prvků haldu. BHDecreaseKey Θ(log N ) Sníží hodnotu klíče prvku. BHIncreaseKey Θ(log2 N ) Zvýší hodnotu klíče prvku. BHDelete Θ(log N ) Smaže prvek. Notací Θ∗ (1) rozumíme amortizovanou složitost.
1.1. Zavedení binomiální haldy Namísto jediného stromu (jako má binární halda) sestává binomiální halda ze sady tzv. binomiálních stromů. Binomiální stromy Definice: Binomiální strom řádu k (značíme Bk ) je zakořeněný strom, pro který platí následující pravidla. 1 strom B0 (řádu 0) obsahuje pouze kořen 2 strom Bk pro k > 0 má kořen, který má právě k synů, přičemž tito synové jsou zároveň kořeny binomiálních stromů po řadě B0 , B1 až Bk−1 . Náhled na strukturu binomiálního stromu získáme z obrázku 1.1. Také se podívejme, jak budou vypadat některé nejmenší binomiální stromy (viz obr. 1.2). B0
B1
B2
B3
B4
Obr. 1.2: Příklady binomiálních stromů 1
2016-09-28
Bk
...
Bk−2
B0 B1
Bk−1
Obr. 1.1: Binomiální strom řádu k Podáme ještě jednu definici binomiálních stromů (tzv. rekurzivní definici binomiálních stromů), pro níž následně ukážeme její ekvivalenci s předchozí definicí. Definice: Zakořeněné stromy Bk0 jsou definovány takto: B00 obsahuje pouze kořen a 0 pro k > 0 se Bk0 skládá ze stromu Bk−1 , pod jehož kořenem je napojený další strom 0 Bk−1 .
= 0 Bk−1 0 Bk−1
Bk0
Obr. 1.3: Rekurzivní definice binomiálního stromu Lemma 1: Stromy Bk a Bk0 jsou izomorfní. Důkaz: Postupujme matematickou indukcí. Pro k = 0 tvrzení zjevně platí. Zvolme k > 0. Pod kořenem stromu Bk jsou dle definice zavěšeny stromy B0 , . . . , Bk−1 . Odtržením posledního podstromu Bk−1 od Bk však dostáváme strom Bk−1 . To dává 0 přesně definici stromu Bk0 . Naopak, uvážíme-li strom Bk0 , z indukce vyplývá, že Bk−1 je izomorfní Bk−1 , pod jehož kořen jsou dle definice napojeny stromy B0 , . . . , Bk−2 . Pod kořen Bk0 jsou tudíž napojeny stromy B0 , . . . , Bk−1 . Lemma 2: Počet hladin stromu Bk je roven k + 1 a počet jeho vrcholů je roven 2k . Důkaz: Dokážeme matematickou indukcí. Strom B0 má jistě 1 hladinu a 20 = 1 vrchol. Zvolme k > 0. Z indukčního předpokladu vyplývá, že hloubka Bk−1 je k a počet vrcholů je 2k−1 . Užitím předchozího lemmatu dostáváme, že strom Bk je složený ze dvou stromů Bk−1 , z nichž jeden je o hladinu níže než druhý, což dává počet hladin k + 1 stromu Bk . Složením dvou stromu Bk−1 dostáváme 2 · 2k−1 = 2k vrcholů. Důsledek: Binomiální strom s N vrcholy má hloubku O(log N ) a počet synů kořene je taktéž O(log N ). 2
2016-09-28
Od stromu k haldě Z binomiálních stromů nyní zkonstruujeme binomiální haldu. Pro uložení N = 2` prvků stačí zvolit strom B` . Pro N 6= 2` využijeme vlastností dvojkového zápisu čísla N : haldu sestavíme z binomiálních stromů takový řádů, pro něž jsou nastaveny příslušné bity v čísle N . Definice: Binomiální halda obsahující N prvků se skládá ze souboru stromů T = T1 , . . . , T` , kde 1 Uchovávané prvky jsou uloženy ve vrcholech stromů Ti . Prvek uložený ve vrcholu v ∈ V (Ti ) značíme h(v). 2 Pro každý strom Ti platí tzv. haldová podmínka, neboli pro každý v ∈ V (Ti ) a jeho syny s1 , . . . , sk platí h(v) ≤ h(sj ), j = 1, . . . , k. 3 Každý strom Ti je binomiální strom. 4 V souboru T se žádné dva řády binomiálních stromů nevyskytují dvakrát. 5 Soubor stromů T je uspořádán vzestupně podle řádu binomiálního stromu. Jako vhodný způsob uložení souboru stromů T tedy poslouží například spojový seznam. Ve spojovém seznamu lze i jednoduše udržovat seznamy synů jednotlivých vrcholů v binomiálním stromě. Tvrzení: Binomiální strom řádu k se vyskytuje v souboru stromů N -prvkové binomiální haldy právě tehdy, když je v dvojkovém zápisu čísla N nastavený k-tý nejnižší bit na 1. Důkaz: Z definice binomiální haldy vyplývá, že binomiální stromy dohromady dávají Pk i i=1 bi 2 = N , kde k je maximální řád stromu v T a bi = 0 nebo bi = 1. Z vlastností zápisu čísla v dvojkové soustavě vyplývá, že pro dané N jsou čísla bi (a tím i řády binomiálních stromů v T ) určena jednoznačně. Čísla bk , bk−1 , . . . , b1 tedy tvoří zápis N v dvojkové soustavě. Důsledek: N -prvková binomiální halda sestává z O(log N ) binomiálních stromů.
1.2. Operace s binomiální haldou Nalezení minima Jak jsme již ukázali u binární haldy, pokud strom splňuje haldovou podmínku, musí se minimum v něm uložené nacházet v jeho kořeni. Minimum cele haldy se tedy musí nacházet v jednom kořenů stromů Ti . Operaci BHGetMin tedy postačí projít seznam T , což bude trvat čas O(log N ). Operaci BHGetMin lze urychlit na čas Θ(1) tím, že binomiální haldu rozšíříme o ukazatel na globální minimum. Při každé další operaci nad binomiální haldou potom tento ukazatel přepočítáme, například průchodem seznamu T . Čtenář nechť si povšimne, že s vyjímkou amortizovaného BHInsert na to každá operace bude mít dostatek času. 3
2016-09-28
Slévání Operaci BHMerge poněkud netypicky popíšeme jako jednu z prvních, protože ji budeme nadále používat jako podproceduru ostatních operací. Algoritmus slévání vezme dvě binomiální haldy a vytvoří z nich jedinou, která obsahuje prvky obou hald a přitom zachovává všechny vlastnosti haldy popsané výše. V první fázi provedeme klasické slití dvou uspořádaných seznamů. Takto slitý seznam bude obsahovat stromy z obou hald, takže se může stát, že od některých řádů budou v seznamu stromy dva. V druhé fázi provedeme konsolidaci , která pospojuje stromy stejných řádů tak, aby zbyl od každého nejvýše jeden. Konsolidace bude probíhat následovně. Připravíme pomocné pole obsahující dlog2 N e+1 přihrádek (číslovaných od 0). Stromy ze seznamu rozdělíme do přihrádek tak, že v i-té přihrádce jsou všechny stromy řádu i. Poté projdeme všechny přihrádky počínaje od 0. Pokud v některé nalezneme alespoň dva stromy, spojíme tyto stromy do jednoho o řád většího stromu a nový strom vložíme do přihrádky s o jedna vyšším indexem. Na konec obsahy přihrádek pospojujeme ve správném pořadí do výsledného spojového seznamu. Algoritmus BHMerge Vstup: Binomiální haldy H1 , H2 Výstup: Binomiální halda Hout poskládaná z prvků H1 a H2 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
Pokud H1 nebo H2 je prázdná: Vyřešíme triviálně a skončíme. (Slévání se nekoná.) Slij seznamy H1 a H2 setříděně do Htmp . Připrav pole P [0 . . . dlog2 |Htmp |e] spojových seznamů. Pro všechny stromy s ∈ Htmp : Odtrhni s ze seznamu Htmp . Vlož s do P [řád (s)]. Hout ← nová prázdná halda Pro všechny přihrádky i v P (počínaje od 0): Pokud má P [i] alespoň dva stromy: b1 , b2 ← odtrhni první dva stromy z P [i]. b ← BHMergeTree(b1 , b2 ) Vlož b do P [i + 1]. Obsah P [i] připoj na konec Hout . Přepočítej v Hout ukazatel na minimální prvek
Spojení dvou stromů, které používáme v předchozím algoritmu je velice jednoduché. Při spojování je potřeba napojit kořen jednoho stromu jako posledního syna kořene druhého stromu. Přitom musíme dát pozor, aby zůstala zachována haldová podmínka, takže vždy zapojujeme kořen s větším prvkem pod kořen s menším prvkem. 4
2016-09-28
Procedura MergeTree Vstup: Stromy b1 , b2 z binomiální haldy (řád (b1 ) = řád (b2 )) Výstup: Výsledný strom bout 1. Pokud kořen(b1 ) ≤ kořen(b2 ): 2. Připoj kořen(b2 ) jako posledního syna pod kořen(b1 ). 3. bout ← b1 4. Jinak: 5. Připoj kořen(b1 ) jako posledního syna pod kořen(b2 ). 6. bout ← b2 Tvrzení: Algoritmus BHMerge je korektní a jeho časová složitost je Θ(log N ). Důkaz: Algoritmus konsolidace používá pouze cykly pevných délek (přes všechny prvky resp. přes všechny přihrádky), takže je zcela jistě konečný. Ukažme, že po konsolidaci nebudou ve výsledném spojovém seznamu dva stromy stejného řádu: V každé přihrádce se nikdy nevyskytují více než tři stromy. Na začátku mohou být nejvýše dva a nejvýše jeden může být přidán po slévání z přihrádky s o jedna menším indexem. Díky tomu je jasné, že po průchodu přihrádkami bude v každé nejvýše jeden strom, takže ve výsledné haldě se nemohou vyskytovat dva stromy se stejným řádem. Složitost slévání je přímo úměrná počtu přihrádek, které vytvoříme. V každé přihrádce jsou nejvýše 3 stromy (tedy konstantní počet) a za každou přihrádku provedeme také nejvýše jedno spojení stromů. Celková složitost v nejhorším případě bude tedy Θ(log N ). Vkládání prvků a postavení haldy Operaci BHInsert vyřešíme snadno. Vytvoříme novou binomiální haldu obsahující pouze vkládaný prvek a následně zavoláme slévání hald. Snadno nahlédneme, že pouhé přeuspořádání stromů při přidání nového prvku tak, aby v seznamu nebyly dva stromy stejného řádu, může v nejhorším případě vyžadovat čas Θ(log N ) operací. Algoritmus BHInsert Vstup: Binomiální halda H, vkládaný prvek x Výstup: Binomiální halda H s vloženým prvkem 1. Vytvoř binomiální haldu Htmp s jediným prvkem x. 2. H ← BHBHMerge(H, Htmp ) Tvrzení: Operace BHInsert má časovou složitost Θ(log N ) worst-case. Pro na počátku N -prvkovou haldu trvá libovolná posloupnost K volání operace BHInsert čas O(N + K); BHInsert má tedy amortizovanou časovou složitost Θ(1). Důkaz: Jednoprvkovou haldu umíme určitě vytvořit v konstantním čase, takže těžiště práce bude ve slévání hald. Slévání zvládneme v čase Θ(log N ), tedy i vkládání prvku bude mít v nejhorším případě logaritmickou časovou složitost. 5
2016-09-28
Slévání dvou hald skutečně pracuje v logaritmickém čase, avšak při vkládání má jedna ze slévaných hald pouze jeden prvek. V nejhorším případě se samozřejmě může stát, že původní halda má všechny stromy od B0 až po Bdlog2 N e−1 , takže při slévání dojde k řetězové reakci a postupně se všechny stromy sloučí do jediného, což si vyžádá Θ(log N ) operací. Nicméně pokud je například počet prvků v původní haldě sudý, pak strom B0 v jejím spojovém seznamu chybí a slévání s jednoprvkovou haldou je možné provést v konstantním čase. Poznamenejme ještě, že při slévání původní a nové jednoprvkové haldy, lze spojení seznamů provést v konstantním čase, takže nás budou z hlediska asymptotické složitosti zajímat pouze operace spojení dvou stromů. Pro amortizovanou analýzu využijeme skutečností dokázaných pro binární sčítačku. Připomeňme, že posloupnost K inkrementů v N -bitové binární sčítačce trvá čas O(N + K). Nyní si všimněme, že slití dvou binomiálních stromů přesně nastane v okamžiku, kdy se v inkrementované binární sčítačče dojde k součtu dvou jedničkových bitu. Počet bitových změn je tak úměrný počtu spojení binomiálních stromů. Z toho už jednoduše vyplývá celková časová složitost O(N + K) pro K volání operace BHInsert. Předešlá amortizovaná analýza operace BHInsert dává návod na realizaci rychlé operace BHBuild pro postavení binomiální haldy opakovaným voláním operace BHInsert. Důsledek: Posloupnost N volání operace BHInsert trvá čas Θ(N ). Všimněme si, že narozdíl od binární haldy, jejíž rychlá stavba vyžadovala speciální postup, zde nám pro rychlé postavení binomiální haldy stačilo pouze lépe analyzovat časovou složitost. Odstranění minima Odstranění minima je nepatrně komplikovanější než vkládání prvků, nicméně opět použijeme operaci BHMerge. Při odstraňování nejprve nalezneme strom M , jehož kořen je minimem, a tento strom odpojíme z haldy. Následně odtrhneme všechny syny (včetně jejich podstromů) kořene M a vložíme je do nové binomiální haldy. Tato operace je poměrně jednoduchá, neboť se mezi syny dle definice binomiálního stromu nikdy nevyskytují dva stromy stejného řádu. Na konec slijeme novou haldu s původní, čímž se odtržené prvky začlení zpět. Algoritmus BHExtractMin Vstup: Binomiální halda H Výstup: Binomiální halda H s odstraněným minimem 1. 2. 3. 4.
m ← strom s nejmenším kořenem v haldě H. Odeber m z H. Vytvoř prázdnou binomiální haldu Htmp . Pro každého syna s kořene stromu m: 6
2016-09-28
5. Odtrhni podstrom s kořenem v s a vlož jej do Htmp . 6. Odstraň m. (Zbyde nám jen kořen, který odstraníme.) 7. H ← BHBHMerge(H, Htmp ) Tvrzení: Časová složitost operace BHExtractMin v N -prvkové binomiální haldě je Θ(log N ). Lepší časové složitosti nelze dosáhnout. Důkaz: Vytvoření dočasné haldy pro podstromy odstraňovaného kořene zabere nejvýše tolik času, kolik podstromů do ni vkládáme – tedy O(log N ). Slévání hald má také logaritmickou složitost, takže celková složitost algoritmu v nejhorším případě je Θ(log N ). Nemůžeme činit žádné předpoklady o tom, kolik synů má kořen obsahující minimum (nejvýše však O(log N ), takže na rozdíl od vkládání zde bude amortizovaná složitost rovna složitosti v nejhorším případě. Dolní odhad složitosti odstraňování minima získáme z dolního odhadu složitosti třídění. Kdyby existoval rychlejší algoritmus na odstranění minima, zkonstruovali bychom rychlejší třídicí algoritmus než O(N log N ) vložením tříděných prvků operací BHBuild do haldy a následně N -násobým odstraněním minima, což by dalo lepší časovou složitost než O(N log N ).
V úvodu této kapitoly jsme uvedli ještě operace BHDecreaseKey, BHIncreaseKey a BHDelete, které dostanou ukazatel na binomiální haldu a ukazatel na prvek v ní, a provedou po řadě snížení jeho klíče, zvýšení klíče a smazání prvku. Tyto operace přenecháme čtenáři jako cvičení 7, 8 a 9. Implementace a srovnání s regulární haldou Nyní je správný čas zeptat se, jaké výhody nám přinese binomiální halda oproti např. klasické binární. Pomineme-li, že binomiální haldy jsou zajímavé z hlediska teoretického, zbývají nám poměrně jasné ukazatele kvality – časová a paměťová složitost. Časové složitosti základních operací přehledně shrnuje následující tabulka (hvězdičkou jsou označeny amortizované složitosti). Operace
binární
d-regulární
binomiální
Přístup k minimu
Θ(1)
Θ(1)
Θ(1)
Vkládání prvku
Θ(log N )
Θ(logd N )
Θ(log N ), Θ∗ (1)
Odstranění minima
Θ(log N )
Θ(d logd N )
Θ(log N )
Binomiální halda se od klasické binární haldy liší pouze v amortizované složitosti vkládání. Zde se ještě sluší připomenout, že binární haldu umíme postavit v lineárním čase, takže pokud bychom prvky nejprve vkládali do prázdné haldy a až po vložení všech prvků je začali odebírat, dostaneme se i s binární haldou na konstantní amortizovanou složitost vkládání. Binomiální halda může mít na druhou stranu navrch v situacích, kdy se často střídají operace vkládání a vypouštění prvků. Abychom mohli řádně porovnat paměťové nároky, potřebujeme nejprve upřesnit jak reprezentovat binomiální strom v paměti. Regulární haldy jsme bez potíží 7
2016-09-28
zvládli uložit do pole. Pokud bychom se pokusili vtěsnat do pole binomiální strom, některé operace (např. spojení dvou stromů) nám značně podraží co do časové složitosti. Zkusíme tedy přímočarý přístup. Jednotlivé uzly stromu budou dynamicky alokované struktury, které provážeme ukazateli. Každý uzel pak bude obsahovat jeden prvek a pole odkazů na všechny své syny. Na první pohled by se mohlo zdát, že na takovou reprezentaci budeme potřebovat poměrně velké množství paměti. Každý uzel může mít až O(log N ) synů, takže celý strom pak zabere O(N log N ) paměti. Pozorný čtenář už jistě tuší, že se jedná pouze o hrubý horní odhad a že by mohl jít ještě vylepšit. Právě polovina uzlů jsouh1i totiž listy a nepotřebují tedy žádnou paměť na odkazy na syny. Naopak pouze jeden uzel (kořen) bude mít log2 N synů. Zkusme se podívat, kolik takových ukazatelů bude v jednom binomiálním stromě. Na každý prvek odkazuje právě jeden ukazatel, takže bez ohledu na to, kolik má který uzel synů, v celém stromě je Θ(N ) ukazatelů. Celková složitost pak bude Θ(N ) na reprezentaci stromů a Θ(log N ) na spojový seznam kořenů, což je ve výsledku Θ(N + log N ) = Θ(N ). V asymptotické paměťové složitosti si tedy binomiální halda v ničem nezadá s klasickou, avšak kvůli potřebě ukazatelů na prvky bude mít binomiální halda horší multiplikativní konstantu. Poslední věc, kterou je třeba vzít v úvahu je složitost implementace. Naprogramovat operace na klasické haldě je mnohem snazší, než naprogramovat haldu binomiální. Je tedy potřeba zvážit, zda se tato práce navíc vyplatí. Cvičení 1. 2. 3. 4.
5.
6.
7. 8. 9. h1i
Přeformulujte všechny definice a operace pro maximovou haldu. Dokažte, že libovolné přirozené číslo x lze zapsat jako konečný součet mocnin dvojky 2k1 + 2k2 + . . . tak, že každé ki 6= kj pro různá i, j. Ukažte, že sčítanců v předchozím cvičení je nejvýše dlog2 xe Upravte algoritmus BHMerge tak, aby nepotřeboval pole přihrádek, ale vystačil s konstantní pomocnou pamětí. Časovou složitost musíte pochopitelně zachovat. U binomiální haldy jsme naznačili, že minimum (přesněji referenci na kořen obsahující minimum) můžeme udržovat stranou, abychom k němu mohli přistupovat v konstantním čase. Upravte operace slití, vkládání prvků a vypouštění minima tak, aby zároveň udržovali odkaz na minimum. Ukažte, že tato práce navíc nezhorší časové složitosti operací. Mějme modifikaci binomiální haldy, ve které jsou stromy setříděné sestupně podle řádu (nikoli vzestupně). Opravte operaci slévání hald pro tuto reprezentaci, abyste přitom zachovali její časovou i paměťovou složitost. Navrhněte operaci BHDecreaseKey s časovou složitostí Θ(log N ). Navrhněte operaci BHIncreaseKey s časovou složitostí Θ(log2 N ). Navrhněte operaci BHDelete s časovou složitostí Θ(log N ). Pokud má strom řád alespoň 1. 8
2016-09-28
1.3. Líná binomiální halda Alternativou k „pilnéÿ binomiální haldě je tzv. líná („lazyÿ) binomiální halda. Její princip spočívá v odložení některých úkonů při vkládání prvků a odstranění minima, dokud nejsou opravdu potřeba. Změny v reprezentaci Líná binomiální halda se téměř neliší od pilné. Pouze povolíme, že se ve v souboru stromů může vyskytovat více stromů stejného řádu. Pro jednoduchost budeme navíc předpokládat, že soubor stromů je uložen v obousměrném kruhovém seznamu. Podívejme se, jaké výhody nám to přinese. Operace slití dvou hald, kterou využívá vkládání prvku i vypuštění minima se značně zjednoduší. Vzhledem k tomu, že se stromy mohou v haldě opakovat, slití není ničím jiným než spojením dvou seznamů, což jistě zvládneme v konstantním čase. Aby ale halda nezdegenerovala v obyčejný spojový seznam, musíme čas od času provést konsolidaci a stromy sloučit tak, aby jich bylo v seznamu co nejméně. Nejvhodnější čas na tento úklid je při hledání minima. Při hledání beztak procházíme všechny stromy v seznamu, takže je můžeme zároveň spojovat. Pozorný čtenář jistě nad předchozím odstavcem pozvedne obočí. Proč bychom nemohli použít stejný trik jako u pilné haldy a pamatovat si neustále ukazatel na strom s nejmenším kořenem? Takové vylepšení by bylo samozřejmě možné a konsolidaci bychom pak prováděli při odstranění minima (místo při hledání). Tímto vylepšením se však nebudeme zabývat a ponecháme jej na rozmyšlenou do cvičení. Konsolidace Konsolidace je velice podobná druhé fázi algoritmu Merge. Všechny stromy rozdělíme do dlog N e + 1 přihrádek (číslovaných od 0) tak, že v i-té přihrádce se budou nacházet všechny stromy řádu i. Bohužel již nemůžeme činit žádné předpoklady o počtech stromů v jednotlivých přihrádkách. Z každé přihrádky budeme tedy odebírat stromy po dvou a slučovat je dokud to bude možné (zbude pouze jeden nebo žádný strom). Algoritmus LazyHeapConsolidation Vstup: Líná implementace binomiální haldy H o N prvcích Výstup: Zkonsolidovaná halda H 1. 2. 3. 4. 5. 6. 7. 8. 9.
Pokud je H prázdná: Konec. Připrav pole P [0 . . . dlog N e] spojových seznamů. Pro všechny stromy s v H: Odtrhni s z H. Vlož s do P [řád (s)]. Pro všechny přihrádky i v P : Dokud má P [i] alespoň dva stromy: b1 , b2 ← odtrhni první dva stromy z P [i]. b ← BHBHMergeTree(b1 , b2 ) 9
2016-09-28
10. 11. 12.
Vlož b do P [i + 1]. Pokud v P [i] zbyl strom s: Odtrhni s z P [i] a vlož jej do H.
Funkčnost algoritmu dokážeme velmi podobně, jako u slévání hald. V každé přihrádce nám zbude nejvýš jeden strom, takže se ve výsledné haldě nemohou nacházet dva stromy stejného řádu. O něco komplikovanější bude analyzovat časovou složitost. Časová složitost konsolidace Tvrzení: Časová složitost konsolidace líné binomiální haldy je Θ(N ) v nejhorším případě a Θ(log N ) amortizovaně. Důkaz: Pokud jsme do haldy jen vkládali, bude se skládat z N jednoprvkových stromů. Všechny stromy musíme nejprve vložit do správných přihrádek (což nám zabereΘ(N )). Následně každý strom buď sloučíme s jiným (tzn. zapojíme pod kořen jiného stromu), nebo jej vložíme do výsledného spojového seznamu. Na to budeme potřebovat opět právě Θ(N ) operací. Samozřejmě bychom neměli zapomenout na inicializaci a procházení všech přihrádek, avšak to nám zabere pouze Θ(log N ), což je menší než výsledná lineární složitost. Na první pohled vidíme, že zřídka kdy bude konsolidace skutečně trvat Θ(N ). Vždy musíme alespoň inicializovat a projít všechny přihrádky, takže konsolidace bude trvat nejméně Ω(log N ). Amortizovanou složitost analyzujeme penízkovou metodou. Zavedeme pravidlo, že každý strom v haldě musí mít neustále uložen na svém účtu jeden peníz. Za tento peníz zvládne zaplatit libovolnou konstantní operacih2i . Spočteme, kolik operací se bude s každým stromem provádět při konsolidaci. Nejprve vložíme každý strom do příslušné přihrádky, což je určitě trvá Θ(1). Na následné spojování stromů můžeme nahlížet tak, že napojujeme jeden strom pod jiný (tedy jeden zanikne a jeden se pouze zvětší). Práci za toto napojení a následný přesun vzniklého stromu do nové přihrádky zaplatíme penízem stromu, který je napojován. Obě tyto operace jsou konstantní a každý strom může být napojen nejvýše jednou. Každý strom tedy ze svého konta zaplatí nejvýše konstantní počet operací. Na konci je potřeba ještě přesunout zbývající stromy do spojového seznamu a také zajistit, aby na svých kontech měly znovu jeden peníz. Na to již nemáme nikde našetřeno a budeme muset tuto složitost vykázat. Zbývajících stromů je však již nejvýš Θ(log N ). Příprava a úklid přihrádek nám zabere také logaritmický čas, takže i vykázaná složitost bude Θ(log N ). Na závěr se ještě podívejme, jak se nám promítnou tyto předpoklady do ostatních operací (vkládání prvku a odstranění minima). h2i
Dokonce libovolné (konstantní) množství konstantních operací, neboť k · Θ(1) = Θ(k) = Θ(1). 10
2016-09-28
Důsledek: Časová složitost vkládání prvku do N -prvkové líné binomiální haldy je Θ(1) worst-case a časová složitost odstraňování minima je Θ∗ (log N ) amortizovaně. Důkaz: Při vkládání prvku vytvoříme jeden strom B0 , kterému dáme do vínku jeden peníz, a ten vložíme do haldy. Všechny úkony zvládneme v konstantním čase, takže celková složitost vkládání je Θ(1). Zde bychom měli zdůraznit, že se jedná o složitost v nejhorším případě, nikoli o amortizovanou složitost, jako tomu bylo u pilné haldy. Při odstraňování minima budeme předpokládat, že neustále udržujeme ukazatel na strom s nejmenším kořenem. Po odebrání minima a opětovném začlenění odtržených podstromů do haldy provedeme konsolidaci, při které ukazatel na minimum aktualizujeme. Po odtržení synů nejmenšího kořene musíme každému z nich dát na konto jeden peníz a vložit je do spojového seznamu. To nám zabere právě Θ(log N ) času. Následná konsolidace bude trvat nejdéle Θ(N ), avšak amortizovaně pouze Θ(log N ), jak jsme již ukázali dříve. Srovnání pilné a líné binomiální haldy Líná binomiální halda má na rozdíl od pilné rychlejší vkládání prvků a garantuje, že i v nejhorším případě nebudeme potřebovat na vložení víc než konstantně mnoho času. Naproti tomu odebrání minima se může díky konsolidaci zpomalit až na Θ(N ) v nejhorším případě. Naštěstí amortizovaná složitost odebírání zůstane na Θ(log N ). Pro přehlednost se podívejme do následující tabulky (hvězdičkou jsou označeny amortizované složitosti): Operace
Pilná halda
Líná halda
Vkládání prvku
Θ(log N ), Θ∗ (1)
Θ(1)
Odstranění minima
Θ(log N )
Θ(N ), Θ∗ (log N )
Význam líné binomiální haldy vzroste především v další kapitole, kde slouží jako předstupeň pro návrh tzv. Fibonacciho haldy. Cvičení 1.
Zjistěte, jak by se změnily složitosti jednotlivých operací, kdybychom v implementaci používali místo obousměrného kruhového seznamu pouze jednosměrný lineární.
2.
Zjistěte, jak by se změnily složitosti jednotlivých operací, kdybychom v implementaci používali místo obousměrného kruhového seznamu pouze jednosměrný lineární a udržovali zároveň ukazatel na poslední prvek seznamu.
3.
Předpokládejme, že bychom chtěli neustále udržovat ukazatel na strom obsahující minimum jako v pilné implementaci. Upravte podle toho všechny operace s haldou.
4.
Ukažte, že provedené modifikace nezhoršily časové složitosti jednotlivých operací. 11
2016-09-28
2. Fibonacciho haldy FIXME: motivace a intro
2.1. De nice haldy Modifikace binomiální haldy Fibonacciho haldy vychází z líné reprezentace binomiálních hald, avšak s lehce upravenou definicí binomiálního stromu. Pro efektivní implementaci DecreaseKey povolíme odtrhávání podstromů. Aby nám ale nevznikaly stromy, které budou příliš široké a málo hluboké (tedy stromy vysokého řádu s malým počtem prvků), zavedeme ještě pravidlo, že od každého vrcholu vyjma kořene může být odtržen nejvýše jeden syn. Pokud je odtržen druhý syn, odtrhneme zároveň vrchol samotný, čímž se z něj stane kořen. Jednotlivé stromy budeme udržovat v obousměrném spojovém seznamu stejně jako v případě binomiální haldy. Podívejme se, jak bude situace vypadat „v nejhoršímÿ případě, kdy je ve stromě nejméně prvků. Představme si klasický binomiální strom řádu k. Každému vrcholu vyjma kořene odtrhneme syna s největším řádem. Takto očesaný strom budeme nazývat Fibonacciho strom a označíme jej Fk , aby se nám nepletl s binomiálními stromy Bk . Fk
...
F0 F0 F1
Fk−3
Fk−2
Obr. 2.1: Fibonacciho strom řádu k Povšimněme si, že kořen tohoto stromu má všechny syny kromě prvního snížené o jeden řád. Díky tomu má také dva syny řádu 0 a nejvyšší řád je k − 2 (nikoli k − 1 jak tomu bylo u binomiálních stromů). Podívejme se, jak bude vypadat několik Fibonacciho stromů nejnižších řádů. F0 a F1 jsou totožné s B0 resp. B1 a první změna je patrná až u F2 . Zamysleme se, zda by se Fibonacciho stromy nedaly popsat podobnou rekurzivní definicí, jako binomiální stromy. U binomiálních platilo, že strom řádu k je složen ze dvou stromů řádu k − 1. V případě Fibonacciho stromů platí, že strom řádu k je složen ze stromů Fk−1 a Fk−2 . 12
2016-09-28
F0
F1
F2
F3
F4
Obr. 2.2: Příklady Fibonacciho stromů
= Fk−1 Fk
Fk−2
Obr. 2.3: Rekurzivní definice Fibonacciho stromu Z rekurzivní definice je nejlépe vidět, proč jsou stromy pojmenovány po Fibonaccim. Stromy řádu 0 a 1 mají právě jeden prvek. Strom řádu k má potom |Fk−1 | + |Fk−2 | prvků. Jinými slovy, počet prvků Fibonacciho stromu řádu k odpovídá k-tému Fibonacciho čísluh1i . Měli bychom také ukázat, že ani Fibonacciho stromů nebudeme potřebovat více než O(log N ) na reprezentaci N prvků. Počet prvků stromu řádu k můžeme spočítat pomocí vzorečku na výpočet Fibonacciho čísel: √ !k+2 √ !k+2 1 1+ 5 1− 5 |Fk | = √ − 2 2 5 Všimněme si exponenciálních členů – první má základ 1.618 a druhý −0.618. První tedy bude asymptoticky dominantní, zatím co druhý bude konvergovat k 0. Vzhledem k tomu, že počet prvků roste exponenciálně s řádem stromu, řád závisí logaritmicky na počtu prvků. Podrobné odvození si dovolíme ponechat do cvičení. Než se pustíme do výkladu základních operací, připomeňme, že Fibonacciho stromy představují dolní odhad na naplnění stromů. Naopak binomiální stromy tvoří horní odhad naplnění a v běžných situacích budou stromy něčím mezi.
2.2. Základní operace Základní operace Fibonacciho haldy se téměř neliší od haldy binomiální. Hlavním rozdílem a zároveň motivací pro použití Fibonacciho haldy je přidání operace h1i
Přesněji řečeno Fibonacciho číslu k + 2, neboť první dva stromy mají velikosti 1 a 2, zatímco Fibonacciho posloupnost obvykle začíná prvky 0, 1. 13
2016-09-28
snížení hodnoty klíče. Pro úplnost ještě připomeňme, že pracujeme s minimovými haldami. Analogicky bychom řešili operaci zvýšení hodnoty klíče v maximové haldě. Algoritmus DecreaseKey je velice přímočarý. Pokud dojde ke snížení klíče, může vzniknout porucha v uspořádání haldy mezi modifikovaným prvkem a jeho otcem. U regulární nebo binomiální haldy bychom tuto poruchu vyřešili vybubláním sníženého klíče nahoru. Zde ale využijeme modifikaci popsanou výše a prvek se sníženým klíčem včetně podstromu jehož je kořenem odtrhneme a vložíme do spojového seznamu mezi ostatní stromy haldy. Algoritmus FibDecreaseKey Vstup: Fibonacciho halda H, prvek x jehož klíč byl snížen Výstup: Upravená halda H 1. 2. 3. 4. 5. 6. 7.
Pokud je x kořen nebo otec(x) ≤ x: Konec. o ← otec(x) Odtrhni x i s podstromem a vlož jej do H. Dokud o není kořen a o již přišel o jednoho syna: tmp ← otec(o) Odtrhni o i s podstromem a vlož jej do H. o ← tmp
Nyní se podíváme na časovou složitost. Kdybychom měli velkou smůlu, dojde při snížení klíče k rozpadu větší části stromu. Po odtržení modifikovaného uzlu odtrhneme také jeho otce, děda atd. Zastavíme se až u kořene, který nemá smysl trhat (stejně bychom ho hned zase vložili). Pokud byl modifikovaný uzel listem, mohli jsme provést až tolik trhání, kolik je výška stromu. Díky tomu, že trhání samotné zvládneme v konstantním čase a strom má nejvýše logaritmickou výšku, bude mít celý algoritmus složitost Θ(logN ). Tím jsme si příliš nepolepšili oproti ostatním haldám. Podívejme se, co nám na to řeknou ještě páni účetní z oddělení amortizace. Stále musíme dodržovat pravidlo, že každý strom v haldě musí mít na svém kontě alespoň jeden peníz, aby mohl zaplatit případnou konsolidaci. Za odtržení podstromu zaplatíme vždy 4 peníze. Jeden peníz bude stát skutečná práce odpojení uzlu ze stromu a jeho opětovné vložení do haldy. Další peníz dostane odtržený strom jako počáteční vklad na svůj účet, aby měl z čeho zaplatit konsolidační poplatek. Zbývající dva peníze dostane bývalý otec odtrženého uzlu jako finanční kompenzaci za odebraného potomka. Všimněme si, že pokud nějakému uzlu odtrhneme dva syny, tento uzel bude mít na svém kontě čtyři peníze (dva za každého syna), takže bude mít dostatek peněz, aby se mohl postavit na vlastní nohy a odtrhnout se od svého otce. Díky tomu zaplatíme za operaci FibDecreaseKey pouze za odtržení snižovaného vrcholu (a to pouze konstantní částku). Všechna další řetězová odtržení budou zaplacena z naspořených peněz jednotlivých vrcholů. Amortizovaná složitost tohoto algoritmu je tedy konstantní. 14
2016-09-28
2.3. Srovnání hald Na závěr ještě shrňme rozdíly časových složitostí všech hald, které jsme zde představili. Amortizované složitosti jsou uvedeny pouze tam, kde to má smysl, a značíme je hvězdičkou. Operace
2-regulární
d-regulární
binomiální
Fibonacciho
Vkládání prvku
Θ(log N )
Θ(logd N )
Θ(log N ), Θ(1)∗
Θ(1)
Odstranění minima
Θ(log N )
Θ(d logd N )
Θ(log N )
Θ(N ), Θ(log N )∗
Snížení prvku
Θ(log N )
Θ(logd N )
Θ(log N )
Θ(1)
Fibonacciho halda přinesla konstantní implementace operací vkládání a snížení prvku, a to i v nejhorším případě. Nevýhodou ovšem je, že odstranění minima může v nejhorším případě zabrat až Θ(N ). Cvičení 1.
Dokažte, že na reprezentaci libovolného počtu prvků potřebujeme O(log N ) Fibonacciho stromů různých řádů. Pro jednoduchost předpokládejte, že počet prvků N jde rozložit na součet různých fibonacciho čísel.
2.
Předpokládejme, že u Fibonacciho haldy používáme drobnou implementační optimalizaci popsanou dříve – halda si udržuje odkaz na strom s nejmenším kořenem, aby k němu mohla přistupovat v konstantním čase. Upravte algoritmus FibDecreaseKey, aby tuto hodnotu aktualizoval.
3.
V algoritmu FibDecreaseKey testujeme podmínku, zda daný uzel neměl již odtrženého syna. Navrhněte, jak takovou informaci u každého uzlu udržovat, a upravte všechny operace (zejména konsolidaci), aby tuto hodnotu korektně aktualizovaly.
4* . Bylo by možné ve Fibonacciho haldě také zrychlit operaci zvýšení klíče (pro minimovou haldu), aby fungovala v konstantním čase? Složitosti ostatních operací musíte zachovat.
2.4. Pou¾ití Fibonacciho hald v grafových algoritmech Na závěr se podívejme na některé příklady použití Fibonacciho hald v klasických grafových algoritmech. Než se do toho pustíme, měli bychom také zvážit praktickou stránku věci. Implementace Fibonacciho hald je značně komplikovanější oproti klasickým 2-regulárním haldám. Navíc spotřebovává více paměti a časové složitosti operací mají výrazně větší konstanty. Jejich použití se tedy zpravidla nevyplatí na malých nebo řídkých grafech, kde nemusí být velký rozdíl mezi konstantní a logaritmickou složitostí. 15
2016-09-28
Hledání nejkratších cest Dijkstrův algoritmus jsme podrobně popsali v kapitole ??. Velmi stručně shrňme jeho činnost. Algoritmus hledá nejkratší cestu v grafu bez záporných hran. Pro každý vrchol udržujeme délku nejlepší dosud nalezené cesty z počátečního vrcholu. Na počátku jsou tyto délky nastaveny na nekonečno, vyjma počátečního vrcholu, který má hodnotu 0. Algoritmus v každém kroku zafixuje vrchol s nejmenší dočasnou vzdáleností od počátku a přepočítá jeho sousedy. Zafixování vrcholu odpovídá nalezení a odebrání minima. Přepočítání sousedů může hodnoty pouze snižovat, na což se hodí operace DecreaseKey. Pokud udržujeme dočasné vzdálenosti v poli, trvá nám nalezení a odstranění minima Θ(N ). Naopak snížení hodnoty v důsledku přepočítávání zabere Θ(1). Celková složitost algoritmu je pak Θ(N 2 + M ). V případě úplného grafu si již moc polepšit nemůžeme, ale pokud je graf řidší (což např. mapy silničních sítí bývají), mohlo by se vyplatit použít haldu. Udržujeme-li dočasné vzdálenosti vrcholů v klasické haldě, zrychlí se nám operace nalezení a odstranění minima na Θ(log N ). Naopak přepočítání každého souseda zafixovaného vrcholu nám podraží rovněž na Θ(log N ). V konečném důsledku bude složitost Θ((N +M ) log N ). S Fibonacciho haldami na tom budeme ještě o něco lépe. Operaci nalezení a odstranění minima provádíme často (N krát), takže si můžeme dovolit počítat s amortizovanou složitostí Θ(log N ). Snížení klíče zvládne Fibonacci v konstantním čase, takže celková složitost bude Θ(N log N + M ). Minimální kostry Dalším příkladem použití je algoritmus na hledání minimální kostry známý jako Jarníkův (Primův) a funguje následovně. Na začátku vezmeme libovolný vrchol, který prohlásíme za základ kostry. K tomuto základu přidáme v každém kroku jeden vrchol a jednu hranu, která do něj vede, dokud nebude obsahovat všechny vrcholy grafu. Přitom vybíráme vždy takovou hranu, která je nejkratší možná. Algoritmus tedy potřebuje neustále udržovat seznam vrcholů, které je možné připojit k základu kostry a nejkratší hrany, které do nich vedou. Při klasické reprezentaci těchto vrcholů v poli nás bude stát nalezení nejbližšího vrcholu Θ(N ) a aktualizace po přidání tohoto vrcholu do základu kostry zvládneme konstantně za každou hranu. Celková složitost tedy bude Θ(N 2 + M ). Opět se zde vynoří otázka velikosti grafu. V případě úplného grafu si opět příliš nepolepšíme. U řídkých grafů můžeme zkusit použít klasickou haldu. S ní se nám operace nalezení nejbližšího vrcholu zrychlí na Θ(log N ). Naopak při procházení sousedů nově přidaného vrcholu můžeme buď přidávat další vrcholy do haldy nebo jim snižovat klíče. Obě tyto operace potřebují Θ(log N ), takže celková složitost bude Θ((N + M ) log N ). Konečně použijeme-li Fibonacciho haldy, zvládneme nalezení vrcholu v Θ(log N ) (amortizovaně) a aktualizace spojené se zpracováním hrany – ať už přidání vrcholu nebo snížení klíče – v čase konstantním. Výsledkem tedy bude složitost Θ(N log N + M ). Fix: ref na kapitolu 16
2016-09-28
Fix!
Cvičení 1.
Naprogramujte Dijkstrův algoritmus s polem, 2-regulární haldou a Fibonacciho haldou. Vyzkoušejte je na různých grafech a sledujte, který bude nejefektivnější.
2.
Nalezněte ještě nějaký algoritmus (nemusí být nutně grafový), kde by mohly Fibonacciho haldy přinést užitek.
17
2016-09-28
