{{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
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
|V|-krat, kdezto DECREASE az|E|-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)
}}
| d-regulární | Leftist | Binomial | Fibonacci | |
| **Definice:**otec≤syn | ||||
| (nebo otec≥syn) |
d-nární strom
|
|
|
| | MIN|O(1)|O(1)|O(1)|O(1)| | DELETEMIN|zahodím kořen, nahradím posledním prvkem a když nesedí probublávám dolů |zahození kořene a zMERGEování jeho synů |zahození kořene, syny vložíme do haldy a zMERGEujeme (☀ jako leftist) |zahodím kořen, syny vložíme do sezn.kořenů, zMERGEujeme stejné řády (☀ jako leftist) | | INSERT|přidám na konec haldy a když nesedí probublávám nahoru |MERGE* *1-prvkové haldy |je vytvoření 1-prvkové haldy a zavolání MERGE (☀ jako leftist) |vložení 1-prvkové haldy do seznamu kořenů (☀ jako leftist) | | DECREASEKEY|snížím číslo a když nesedí probublávám nahoru |snížím číslo odříznu od zbytku haldy, a **MERGE **podstromu a zbytku |snížím číslo a když nesedí probublávám nahoru (☀ jako d-reg) |urveme podstrom se zmenšeným prvkem,dáme do lesa, rekurzivně: pokud někde urveme 2.syna nekořenu urveme i ten prvek | | MERGE|(MAKEHEAP) vytvoříme z prvků náhodný d-reg.strom a postupně probubláváme dolů každý ne-list |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 |(pro ∀stromy) rekurzivně slep 2 stromy stejného řádu, menší kořen přilepím jako syna toho co má vyšší kořen |(2 stromy st.řádu) menší kořen přilepím jako syna toho co má vyšší kořen (☀ jako binom) |