{{zkazky|
* '''Fibonacciho haldy (2014, Hladík)''' - Lehce nečekané (jedna z těch věcí, kde si člověk říká o haldách člověk něco řekne ale pak ...). Začal jsem úvodem co jsou haldy, napsal něco o Leftist, D-Reg., Polynom a nakonec Fibonachi. Popis struktury (les) a omezení (oproti poly. je rozvoleněné), jak pracuje "konsolidace" (spojování stromů stejných stupňů), označení vrcholů, vztah k Fibonacciho číslům. Popsání operací insert, merge, delete, delete-min + v diskusi pak složitosti. Padla otázka na definici .?. nakonec to prošlo +- přes "operace". Zmínění ostatních hald pan Hladík nejprve při diskusi přeskočili (neb to nebylo otázkou), ale dalo se na ně hezky referovat pro "porovnání".
* '''Fibonacciho haldy (2013, Hladík)''' - Základně jsem popsal d-regulární a binomiální haldy a složitost operací (to ho moc nezajímalo). Pak, že FH jsou definované pomocí posloupnosti operací + popis operací (stačilo slovně). Trochu jsem plaval v dokazování složitosti (stačila amortizovaná), ale důležité bylo ukázat, že vím, proč jsou ty operace definované tak, jak jsou (jak ovlivňují složitost). Nakonec dotaz, kde se využívají a jaké mají výhody proti ostatním strukturám/haldám. Celkově byl zkoušející v pohodě.
* '''Haldy (2012, Koubkova)''' - Regularni haldy -- co jsou, k cemu jsou, Min/Max heap, Insert, ExtractMin, Delete, pouziti, implementace v poli, Binomiální haldy, Fibbonaciho haldy, nasledne diskuse
* '''Haldy (2012, Žemlička)''' - Popsal jsem binární (s tím, že je tom jenom jednoduchý případ d-regulární), binomiální, a Fibonacciho, u Fibonacciho jsem si nebyl jistý, jak se počítá amortizovaná složitost, protože mi vycházelo, že by mohla být konstantní, ale Žemličkovi se to nechtělo moc řešit, tak se mě zeptal, kdy bych kterou haldu použil a jaké mají prostorové náročnosti a byl spokojený.
* '''Haldy a trie (2011, Kopecky)''' - priznam se, ze me celkem zaskocilo, ze jsem nedostal jen jeden/dva typy hald, respektive ze k tomu byly i trie. Pan Kopecky se zeptal, za jak dlouho to asi bude trvat, nacez jsem odpovedel, ze pokud mam napsat vse, co vim tak asi hodinu a pul Navrhl jsem zkouseni "on-the-fly", protoze toto jsem celkem umel, ale pan Kopecky chtel byt korektni a nechal mi tedy asi 20min na pripravu, to jsem stale psal a tak tedy vzhledem k pokrocile dobe prikyvnul, ze mu to mam povykladat to co mam na papire + treba neco kolem. Probrali jsme tedy d-regularni haldy, binomialni, tam jsme to cele ani nedodelali, zacal jsem fibinacciho a tam bylo prohlaseno, ze to umim a ze to staci. Coz jsem byl rad, protoze trie jsem umel uz mene Znamka: 1
* '''Haldy (2011, Majerech)''' - Co a jak zkouší: Dobrý je přehled o haldách obecně (co od nich nejlepšího můžu očekávat, jakou asymptotickou/amortizovanou složitost). Logaritmus tam vždy u nějaké operace vždy bude. d-reg. haldy prý nesnáší, ale v klidu je zkoušel. Odráží se totiž od toho, co máte napsané. Řekl, že nemám zmiňovat leftist haldy, když nevím, jak vypadají, že by se na to neptal.
* '''Haldy a fibonacciho haldy (2010, Fiala)''' - asi na 3/4 stranu som si rozpísal d-reg., bionom. a lazy. binom haldy (čo to je, aké sú tam operácie, ako približne fungujú, aká je cca. (amortizovaná) O() :)), na fibonacciho mi ostalo pár riadkov na konci... väčšinu odpovede som strávil zbežnými komentármi k haldám, takže po pár minútach som asi vyčerpal trpezlivosť a pri fibonacciho sme len prediskutovali, aké majú výhody (decrease/increase key, delete, O(1) atď...) a bolo hotovo..
* '''Haldy (2010, Koubkova)''' - d-regularni, binomialni, leftist, fibbonaci. Ukazat pridavani / odebirani prvku v d-regularni a binomialni.
* '''Haldy (2009, Čepek)''' - Definice + operace binární haldy, binomiální haldy, Fibonacciho haldy + dotaz, jak se (implementačně) řeší přístup na prvek haldy (třeba fuprostřed nějakého stromu Fib. haldy (Odpověď: pole ukazatelů do haldy indexované čísly vrcholů)
I1/I4:
* '''Fibonacciho haldy (2014, Koubek) -''' Další nemilá otázka, navíc jsem podcenil přípravu na papír, kterou Koubek podrobně zkoumal. Čekal jsem, že to doplním během diskuze, ale nedostal jsem moc šanci. Pokud vás bude zkoušet, raději si vezměte víc času na přípravu na papír a pořádně to tam napište. Koubek je puntičkář a<nowiki> </nowiki>nelíbí se mu, když člověk zapomíná předpoklady k tvrzením, apod. Koubek byl velmi zklamaný, nakonec mi dal 3-, že se mám ještě snažit.
* '''Haldy (2013, MJ)''' - Popsal jsem definice a (hodne) strucne i operace. D-reg se vsim vsudy, i dotaz na vysku stromu. Leftist haldy byly jen s definici a popiskem, ze se vyvazuji utrzenim podstromu a prohazovanim synu. Binomialni v pohode bez dukazu (stacilo rict <math>|B_i| = 2^i</math>). Line haldy - motal jsem se v amort. slozitosti, takze me nechali ji spocitat, jinak by to ale asi slo i bez ni. Fibonacciho opet bez dukazu, jen jsem opet motal amort. slozitost, tak jsem jim ji radsi spocital. Pak chteli nejake aplikace - heapsort, dijkstra. Pro me novy poznatek: "Proc bychom mohli chtit u d-reg hald zvysovat d? Kdyz nas nezajimaji nejake male konstanty, tj. ty hodnoty mezi 4-6, o kterych se pise, ze jsou idealni pro vnitrni trideni?" Odpoved znela, ze v Dijkstrovi pouziju DELETEMIN jen <nowiki>|V|</nowiki>-krat, kdezto DECREASE az <nowiki>|E|</nowiki>-krat. Zvetseni d mi sice zhorsi DELETEMIN (bublani dolu je kvuli vice synum pomalejsi), ale zase zlepsi DECREASEKEY (haldy jsou mensi).
* '''Haldy (2012, Koubek)''' - popsal jsem d-regulární haldy, zmínil jsem se o tom, že existují leftist haldy a popsal jsem binomiální haldy. Pana profesora ale zajímaly hlavně Fibonacciho haldy, jejichž složitost jsem nedokázal uspokojivě vysvětlit. Doporučení: ty algoritmy si OPRAVDU projděte.
* '''Fibonacciho haldy (Koubek)'''
}}
{| class="wikitable"
|-
!
! d-regulární
! Leftist
! Binomial
! Fibonacci
|-
|'''Definice:'''otec≤syn
(nebo otec≥syn)
| class="darybg" |
d-nární strom<br>
* '''∀uzel''' má '''nejvýše d synů'''
* je '''"shora a zleva" naplněný''' (☀ jakobyste ten strom měli v poli a do něj zleva nasypali souvislý blok prvků)
Operace založeny na '''probublávání'''[[Soubor:Dary heap.png|frameless|160x160px]]
| class="leftistbg" |
binarni strom (''línější ''podmínky než d-reg)
* vrchol má '''1 syn'''a '''⇒''' je to '''levý syn'''
* jinak '''npl(levého syna) ≥ npl(pravého)'''<br>
* '''npl(v) '''- (null path lenght)je '''delka nejkratsi cesty''' z vrcholu v '''do vrcholu s max. 1 synem '''(∼délka pravé cesty v podstromě - kvůli 1.bodu)
Operace jsou "rekurzivněji" založeny na '''MERGE''' a '''DECREASEKEY'''.
| class="binombg" |
[[Soubor:Binom.png|right|frameless|90x90px]]les binomiálních stromů
* ∀'''řád max. 1'''
* '''binomiální strom''' řádu ''i'' se skládá z kořene a synů ze stromů izomorf. řádu ''0,...,i-1'' - chová se jako malá halda (☀H<sub>0</sub> je 1 uzel)<br>
"''Horlivé''" operace založené na '''MERGE'''
| class="fibbg" |
'''les '''(2směrný spoják) i-nárních '''hald''' vzniklých posloupnosti operací pro fib.haldy
* '''označení vrcholu že ztratil syna''' - z nekořenového prvku lze oddelit max 1 syna, jinak se oddeli cely uzel do noveho stromu
* '''řád stromu''' - počet synů kořene (řády se '''mohou''' opakovat a podstrom má alespoň ''F<sub>i+1</sub>'' vrcholů)
* pointer na min.kořen
"''Líné''" operace.
|-
| '''MIN'''
|style="background:#ddffdd"| ''O''(1)
| style="background:#ddffdd" | ''O''(1)
| style="background:#ddffdd" | ''O''(1)
| style="background:#ddffdd" | ''O''(1)
|-
| '''DELETEMIN'''
| style="background:#ffffdd" | zahodím kořen, '''nahradím posledním prvkem''' a když nesedí '''probublávám dolů'''
''O''(d log ''n'')
| style="background:#ffffdd" | zahození kořene a zMERGEování jeho synů
''O''(log ''n'')
| style="background:#ffffdd" | zahození kořene, syny vložíme do haldy a zMERGEujeme (☀ jako leftist)
''O''(log ''n'')
| style="background:#ffffdd" | zahodím kořen, syny vložíme do sezn.kořenů, zMERGEujeme stejné řády (☀ jako leftist)
''O''(log ''n'')<ref name="amortized">Amortized time.</ref>
|-
| '''INSERT'''
| style="background:#ffffdd" | '''přidám na konec haldy''' a když nesedí '''probublávám nahoru'''
''O''(log ''n'')
| style="background:#ffffdd" | MERGE'' ''1-prvkové haldy
''O''(log ''n'')
| style="background:#ddffdd" | je vytvoření 1-prvkové haldy a zavolání MERGE (☀ jako leftist)
''O''(1)<ref name="amortized" />
| style="background:#ddffdd" | vložení 1-prvkové haldy do seznamu kořenů (☀ jako leftist)
''O''(1)
|-
| '''DECREASEKEY'''
| style="background:#ffffdd" | snížím číslo a když nesedí '''probublávám nahoru'''
''O''(log ''n'')
| style="background:#ffffdd" | snížím číslo '''odříznu od zbytku haldy''', a '''MERGE '''podstromu a zbytku
''O''(log ''n'')
| style="background:#ffffdd" | snížím číslo a když nesedí '''probublávám nahoru''' (☀ jako d-reg)
''O''(log ''n'')
| style="background:#ddffdd" | urveme podstrom se zmenšeným prvkem,dáme do lesa, rekurzivně: pokud někde urveme 2.syna nekořenu urveme i ten prvek
''O''(1)<ref name="amortized" />
|-
| '''MERGE'''
| style="background:#ffdddd" | (MAKEHEAP) vytvoříme z prvků náhodný d-reg.strom a postupně probubláváme dolů každý ne-list
''O''(d² ''n'')
| style="background:#ffffdd" |zavolá MERGE(pravý podstrom T1 s menším klíčem v kořeni, T2) výsledek připojí místo onoho pravého syna. Pokud neplatí '''npl''', vymění syny T1
''O''(log ''n'')
| style="background:#ffffdd" | (pro ∀stromy) rekurzivně slep 2 stromy stejného řádu, menší kořen přilepím jako syna toho co má vyšší kořen
''O''(log ''n'')
| style="background:#ddffdd" | (2 stromy st.řádu) menší kořen přilepím jako syna toho co má vyšší kořen (☀ jako binom)
''O''(1)
|}
'''haldy''' - stromová struktura kde platí uspořádání na haldě:
* otec≥syn (tzv. max-heap) nebo
* otec≤syn (tzv. min-heap)
** 💡 tj. max/minimálni prvek je vždy kořen stromu
Haldy se používají pro měnící se uspořádané množiny. Nevyžaduje se efektivní operace '''MEMBER''' (často se předpokládá s argumentem operace informace o uložení prvku). Požadují se malé nároky na paměť ( O(n) ) a rychlost ostatních operací. ('''MIN''' v O(1))
jsou různě rychlé ale vždy aspoň 1 operace má složitost O(log n)
Krom běžných operací můžu měnit uspořádání: operace '''INCREASE''' a '''DECREASE''' změní velikost klíče o 1.
[[Soubor:Dary heap.png|thumb|d-regulární halda|400x400px]]
=== d-regulární haldy ===
'''Pravidla (minheap):'''
* ∀ vrchol má '''nejvýše d synů'''
* vrchol není list ⇒ ∀vrchol s menším číslem má právě d synů (očíslování vrcholů - odzhora dolu, zleva doprava)
* vrchol má synů < d ⇒ ∀vrcholy s většímy čísly jsou listy
* d-reg.strom má max 1 vrchol, který není list a má synů < d
'''Hloubka:''' zřejmě ⌈log<sub>d</sub> (n(d-1)+1)⌉
💡 umožňuje i efektivní reprezentaci v poli
'''MAKEHEAP '''(také se používá pro '''MERGE''') -''' '''vytvoříme z prvků lib. d-reg.strom a postupně posouváme dolů každý ne-list, nejh.čas O(d² n)
'''INSERT '''- '''přidám na konec haldy''' a když nesedí prohazujeme s rodičem (tedy '''posouvám nahoru UP''') , O(log<sub>d</sub> n)
'''DELETE / DELETEMIN '''- odeberu, '''nahradím posledním prvkem''' a pokud nesedí prohazuji s potomky kteří porušují vlastnost víc (tedy '''posouvám nahoru nebo dolů UP/DOWN''') , O(d log<sub>d</sub>n)
'''DECREASE '''- '''zvětším číslo o a''' a když nesedí prohazujeme s rodičem (tedy '''posouvám nahoru UP''') , O(log<sub>d</sub> n)
'''Aplikace'''
''Heapsort'' -- vytvoření haldy a postupné volání '''MIN''' a '''DELETEMIN'''. Lze ukázat, že pro <math> d=3,d=4\,\!</math> je výhodnější než <math> d=2\,\!</math>, empiricky je do cca <math> 1 000 000\,\!</math> prvků <math> d=6\,\!</math> nebo <math> d=7\,\!</math> nejlepší. Pro delší posloupnosti je možné <math> d\,\!</math> zmenšit.
''Dijkstra'' -- normální Dijkstrův algoritmus, jen vrcholy grafu uchovávám v haldě, tříděné podle aktuálního <math> d\,\!</math> (horního odhadu vzdálenosti). Složitost <math> O((m+n)\log n)\,\!</math>, pro <math> d=\max\{2,\frac{m}{n}\}\,\!</math> je to <math> O(m\log_d n)\,\!</math> a pro husté grafy (<math> m>n^{1+\varepsilon}\,\!</math>) je lineární v <math> m\,\!</math>.
zdroje
* https://www.youtube.com/watch?v=WCm3TqScBM8
[[Soubor:Leftist.png|thumb|leftist|342x342px]]
=== Leftist haldy ===
binarni strom
* vrchol má 1 syna ⇒ je to levý syn
* vrchol má 2 syny ⇒ npl(levého syna) ≥ npl(pravého)
** '''npl(v) '''- (null path lenght)''' '''je '''delka pravé''' (nejkratsi)''' cesty''' z vrcholu v '''do vrcholu s max. 1 synem '''(délka '''pravé '''cesty v podstromě - defakto kvůli 1.bodu)
* plati usporadni na halde
Pro leftist haldu se definuje pravá cesta (posl. pravých synů) a pokud máme takovou cestu délky <math> k\,\!</math> z vrcholu <math> v\,\!</math>, víme, že podstrom <math> v\,\!</math> do hloubky <math> k\,\!</math> je úplný binární strom. Délka pravé cesty z každého vrcholu je tedy logaritmická ve velikosti podstromu.
Operace jsou založeny na algoritmech '''MERGE''' a '''DECREASE'''.
'''MERGE(T1,T2)''' (💡 rekurzivní)
* Testuje prázdnost obou stromù (a pokud je jeden prázdný, vrátí ten druhý jako výsledek)
* volá MERGE(podstrom pravého syna stromu T1 s menším klíčem v kořeni, T2)
* výsledek připojí místo onoho pravého syna
* Pokud neplatí podmínka na npl, vymění syny T1
'''INSERT(x)''' - je vytvoření jednoprvkové haldy a zavolání MERGE
'''DECREASE(s,a)''' - se udělá snížením hodnoty ve vrcholu '''s''' o '''a''', zavoláním OPRAV, tj. jeho odříznutím od zbytku haldy, a MERGE podstromu a zbytku.
* '''OPRAV(T,v)''' odtrhne podstrom a dopočítá všem vrcholům správné npl. Po odtržení vrcholu a příp. přehození pravého syna doleva jde nahoru dokud provádí změny npl (možno až do kořene), vztahuje npl odspoda a příp. prohazuje syny.
'''vše v nejh.případě O(log n)'''
Ostatni
* MIN je vypsání kořene, DELETEMIN je zMERGEování synů kořene (a jeho zahození). MAKEHEAP je vytvoření hald z jednotl. prvkù, jejich nacpání do fronty a potom v cyklu: vyberu dva z fronty, zmerguju a hodím výsledek zpátky; dokud mám ve frontě víc než 1 haldu - to je potom výsledek.
* MAKEHEAP potřebuje jen O(n)
{{image|image=Bin merge.png|width=200|caption=MERGE}}
{{image|image=Binomial heap.png|width=360|caption='''Binomiální halda''' - les binomiálních stromů}}
=== Binomiální haldy ===
les binomiálních stromů
* každý řád max.jednou,
* binom.strom řádu ''i'' se skládá z kořene a synů ze stromů izomorf. řádu ''0,...,i-1'' - chová se jako malá halda
** 💡 používá se ukazatel na strom s min.prvkem O(1) a kořeny jsou spojene ve spojaku
Operace jsou založené na '''MERGE'''
'''MERGE''' (přes všechny stromy)
* pracuje stejně jako binární sčítání - za pomoci operace SPOJ (slepení dvou stromù, přilepím jako syna toho, který má v kořeni vyšší klíč) '''slepí jen stromy stejného řádu''' (jinak také CONSOLIDATE), přenáší výsledky do dalšího spojování
* vytvoří strom: Hi / Hi
* Složitost - O(log |S1| + log |S2|), protože 1 krok (SPOJ) je konstantní.
'''INSERT''' - je vytvoření jednoprvkové haldy a zavolání MERGE (jako leftist)
'''DECREASE''' - INCREASE a DECREASE změní hodnotu f u prvku a zavolají probublávaní nahoru nebo dolů
vše vyžaduje čas '''O(log n) '''jen INCREASE O(log<sup>2</sup>n)
není podporováno DELETE, jen jako DECREASE + DELETEMIN.
umožňuje rychlou implemetaci Insert O(log n) (amotizovaně O(1)) a Merge (dvou hald) O(log n)
'''Líné binomiální''' - může obsahovat více stejných binomiálních stromů, vyvažování (konsolidace) se děje jen po/před Min a DeleteMin, konsolidace (poskládání dohromady do podoby definované normálníma bin. haldama) - složitost se rozpočítá
[[Soubor:Fib heap.png|thumb|Počty vrcholů stromů F0, F1, … mají souvislost s Fibonacciho čísly (odpovídají jim)
|280x280px]]
=== Fibonacciho haldy (3×🎓) ===
* les haldových stromů vzniklých posloupnosti operací pro fib.haldy z prázné haldy, vychází z (líných) binomiálních
** 💡 výhodou je nízká složitost algoritmů, struktura je více flexibilní, operace co nejsou nutné odkládáme
** 💡 používá se ukazatel na strom s min.prvkem O(1) a kořeny jsou spojene ve spojaku
* při odebírání prvků lze oddelit z nekořenového prvku max 1 syna, jinak se oddeli cely uzel do noveho stromu
** z čehož vyplývá:'' v'' je vrchol a má ''i'' synů ⇒ pak podstrom ''v'' má alespoň ''F<sub>i+1</sub>'' vrcholů
* při '''DELETEMIN''' se počet stromů naopak snižuje - spojují se
** strom má ''rank''(''i'') pokud má kořen ''i'' synů (jako izomorfismus u binom.hald)
* '''MERGE''' - (přes 2 stromy stejných stupňu) přilepím jako syna toho co má vyšší klíč
* '''INSERT '''- je vytvoření jednoprvkové haldy a zavolání MERGE (jako leftist)
* '''MIN '''- projiti korenu a vypsani nejmensiho, můžeme si udržovat odkaz na min (pak je to v O(1))
** '''MIN,MERGE, INSERT, DECREASE''' mají amort.složitost '''O(1)'''
* '''DELETEMIN''' - odebrání stromu s nejmenším prvkem, a pridani jeho podstromu do lesa, pak projdeme a hledame stromy se stejným rank a voláme na ně '''MERGE''' (jinak také <u>CONSOLIDATE</u>, jako líne binom.haldy)
* '''DECREASE, INCREASE a DELETE''' vycházejí z leftist hald.
** Když vrchol není kořen a byl mu předtím někdy odříznut syn, je speciálně označený.
** Používají pomocnou operaci VYVAZ2, která prochází od daného vrcholu ke kořeni a dokud nalézá označené vrcholy, odtrhává je i s jejich podstromy, ruší jejich označení a vkládá do haldy jako zvláštní stromy. DECREASE pak odtrhne podstrom určený snižovaným vrcholem (není-li to už kořen), zruší u něj případné označení a vloží ho zvlášť do haldy, potom volá na odtržené místo VYVAZ2. INCREASE provede to samé, jen ještì roztrhá podstrom zvedaného vrcholu (odtrhne všechny syny, zruší jejich příp. oznaèení a vloží jako samostatné stromy do haldy) a vloží zvednutý vrchol do haldy zvlášť. DELETE je to samé co INCREASE, bez přidání vrcholu zpìt do haldy.
*** '''DELETEMIN,INCREASE,DELETE''' mají amort.sl. '''O(log n)'''
'''Aplikace'''
''Fibonacciho haldy'' se díky své rychlosti '''INSERT''', '''DECREASE''' a '''DELETEMIN''' často používají v grafových algoritmech. Praktické porovnání rychlosti s jinými haldami však není dosud přesně prostudováno.
Motivací pro vývoj ''Fibonacciho hald'' byla možnost '''aplikace v Dijkstrově algoritmu'''. Dává totiž složitost celého algoritmu <math> O(m+ n\log n)\,\!</math>, což by mělo být lepší pro velké, ale řídké grafy proti <math> d\,\!</math>-regulárním haldám. O prakticky zjištěném "zlomu" ale nevíme.
{{zdroje|
* https://www.youtube.com/watch?v=G1BjDafZpqA
}}
