{{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 |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)'''
}}
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ěť a rychlost ostatních operací.
==== Definice, operace ====
Halda je stromová struktura nad množinou (dat) <math>S\,\!</math>, jejíž uspořádání je dáno funkcí <math> f:S\to \mathbb{R}\,\!</math>, splňující ''lokální podmínku haldy'':
:<math> \forall v\in S: f(\,\!</math>otec<math> (v))\leq f(v)\,\!</math>, případně v duální podobě.
Množina ''je reprezentovaná'' haldou, když přiřazení prvků vrcholům haldy je bijekce, splňující podmínku haldy. Různé druhy hald se liší podle dalších podmínek, které musí splňovat stromové struktury.
* Krom běžných operací můžu měnit uspořádání: operace '''INCREASE''' a '''DECREASE''' změní velikost <math> f\,\!</math> na nějakém daném prvku <math> s\,\!</math> se známým uložením o <math> +a\,\!</math>, <math> -a\,\!</math>.
* Další operace: '''DELETEMIN''' -- smazání prvku s nejmenší hodnotou <math> f\,\!</math>.
* Pro operaci '''DELETE''' budeme požadovat přímé zadání uložení prvku.
* Navíc definujeme operaci '''MAKEHEAP''' -- vytvoření haldy při známé množině a <math> f\,\!</math>,
* a ''' MERGE''' -- slití dvou hald do jedné, reprezentující <math> S_1 \cup S_2\,\!</math> a <math> f_1\cup f_2\,\!</math>, aniž by se ověřovala disjunktnost.
===Regulární haldy===
Pro <math> d\,\!</math>-regulární strom (<math> d\in\mathbb{N}\,\!</math>) s kořenem <math> r\,\!</math> platí, že existuje pořadí synů vnitřních vrcholů takové, že očíslování prohledáváním z <math> r\,\!</math> do šířky splňuje:
# každý vrchol má nejvýše <math> d\,\!</math> synů
# když vrchol není list, tak všechny vrcholy s menším číslem mají právě <math> d\,\!</math> synů
# má-li vrchol méně než <math> d\,\!</math> synů, pak všechny vrcholy s většími čísly jsou listy
Potom takový strom s <math> n\,\!</math> vrcholy má max. jeden ne-list, který nemá právě <math> d\,\!</math> synů, jeho výška je <math> \lceil\log_d(n(d-1)+1)\rceil\,\!</math>. Čísla synů vrcholu s číslem <math> k\,\!</math> jsou <math> (k-1)d+2,\dots,kd+1\,\!</math>, číslo otce je <math> 1+\lfloor\frac{k-2}{d}\rfloor\,\!</math>. Takto vytvořená halda umožňuje i efektivní reprezentaci v poli.
==== Operace na regulárních haldách ====
* Není známa efektivní operace '''MERGE'''.
* Máme pomocné operace '''UP''', '''DOWN''', posunující prvek níž/výš ve struktuře, dokud není splněna podmínka haldy ("probublávání").
* '''INSERT''' jen vloží nový prvek za poslední a spustí '''UP'''
* '''DELETE''' nahradí odstraněný prvek posledním listem a volá '''UP''' nebo '''DOWN''' podle potřeby
* '''DELETEMIN''' odstraní kořen, nahradí ho posl. listem a volá '''DOWN'''
* '''MIN''' jen vrátí kořen
* '''INCREASE''' a '''DECREASE''' změní hodnotu <math> f\,\!</math> nějakého prvku a zavolají '''DOWN''', resp. '''UP''' (pozor, je to naopak, než názvy napovídají).
* Operace '''MAKEHEAP''' vytvoří libovolný strom a pak postupně od posledního ne-listu ke kořeni volá na všechno '''DOWN'''.
U všech operací je korektnost zajištěna podmínkou haldy (a tím, že '''UP''' a '''DOWN''' zaručí její splnění).
====Složitost operací====
Běh '''DOWN''' vyžaduje <math> O(d)\,\!</math> a '''UP''' <math> O(1)\,\!</math> v každém cyklu, takže celkem jde o <math> O(d\log|S|)\,\!</math> a <math> O(\log|S|)\,\!</math>.
Haldu lze vytvořit opakovaným '''INSERT'''em v čase <math> |S|\log|S|\,\!</math>, ale pro větší množiny je rychlejší '''MAKEHEAP''' -- uvažujeme-li, že operace '''DOWN''' vyžaduje čas odpovídající výšce vrcholu. Ve výšce <math>k-i\,\;</math> je <math>d^i\,\;</math> vrcholů. Tím dostávám celkový čas <math> O(\sum_{i=0}^{k-1}d^i(k-i)d)\,\!</math>, což se dá odhadnout jako <math> O(d^2|S|)\,\!</math>.
====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>.
===Leftist haldy===
Leftist halda je binární strom (<math> T,r\,\!</math>). Označme npl(<math> v\,\!</math>) délku nejkratší cesty z <math> v\,\!</math> do vrcholu s max. 1 synem. Leftist halda musí splňovat následující podmínky:
# má-li vrchol 1 syna, pak je vždy levý
# má-li 2 syny <math> l,p\,\!</math> , pak npl(<math> p\,\!</math>)<math> \leq\,\!</math>npl(<math> l\,\!</math>)
# podmínka haldy na klíče prvků (ex. přiřazení prvků vrcholům stromu)
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''' testuje prázdnost jednoho ze stromů (a pokud je jeden prázdný, vrátí ten druhý jako výsledek). Pokud ne, volá se rekurzivně na podstrom pravého syna kořene s menším klíčem dohromady s celým druhým a výsledek připojí místo onoho pravého syna. Pokud neplatí podmínka na npl, syny vymění.
* '''INSERT''' je to samé co vytvoření jednoprvkové haldy a zavolání '''MERGE'''.
* '''DELETEMIN''' je z'''MERGE'''ování synů kořene (a jeho zahození).
* '''MAKEHEAP''' je vytvoření hald z jednotl. prvků. Nacpu je do fronty a potom v cyklu vyberu dva první, zmerguju a hodím výsledek na konec, dokud mám ve frontě víc než 1 haldu.
'''INCREASE''' a '''DECREASE''' se dělají jinak.
* Mám pomocnou operaci '''OPRAV''', která 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.
* '''DECREASE''' se pak udělá snížením hodnoty ve vrcholu, zavoláním '''OPRAV''', tj. jeho odříznutím od zbytku haldy, a '''MERGE''' podstromu a zbytku.
'''INCREASE''': zapamatuju si levý a pravý podstrom vrcholu s mým prvkem a provedu na něj '''OPRAV''' (vyhodím ho), potom vyrobím nový vrchol s mým prvkem se zvednutou hodnotou a jako samostatnou haldu ho z'''MERGE'''uju s levým podstromem. Pravý podstrom z'''MERGE'''uju se zbytkem haldy a nakonec s tím z'''MERGE'''uju výsledek '''MERGE''' levého podstromu a zvednutého prvku.
====Složitost====
1 běh '''MERGE''' bez rekurze je <math> O(1)\,\!</math>, hloubka rekurze je omezena pravými cestami, takže je to <math> O(\log(|S_1|+|S_2|))\,\!</math>. Z toho plyne logaritmovost '''INSERT''' a '''DELETEMIN'''.
Pro '''MAKEHEAP''' se uvažuje, kolikrát projdou haldy frontou: po <math> k\,\!</math> projití frontou mají velikost <math> 2^{k-1}\,\!</math> a tedy fronta obsahuje <math> \lceil\frac{|S|}{2^{k-1}}\rceil\,\!</math> hald. Jeden '''MERGE''' je <math>O(k)</math> a jedno projití frontou pro všechny haldy tedy trvá <math> O(k\lceil\frac{|S|}{2^{k-1}}\rceil)\,\!</math>. Celkem dostávám <math> O(|S|\sum_{k=1}^{\infty}\frac{k}{2^{k-1}})=O(|S|)\,\!</math> (součet řady je <math> 4\,\!</math>).
'''OPRAV''' chodí jen po pravé cestě, takže má logaritmickou složitost. '''INSERT''', '''INCREASE''' a '''DECREASE''' se díky ní dostanou taky na <math> O(\log|S|)\,\!</math>, protože jejich části kromě '''MERGE''' a '''OPRAV''' mají konstantní složitost.
===Binomiální haldy===
''Binomiální stromy'' se definují rekurentně jako <math> H_i\,\!</math>, kde <math> H_0\,\!</math> je jednoprvkový a <math> H_{i+1}\,\!</math> vznikne z dvou <math> H_i\,\!</math>, kdy se kořen jednoho stane dalším (krajním) synem kořenu druhého. Pak strom <math> H_i\,\!</math> má <math> 2^i\,\!</math> prvků, jeho kořen má <math> i\,\!</math> synů, jeho výška je <math> i\,\!</math> a podstromy určené syny kořene jsou právě <math> H_{i-1},\dots,H_0\,\!</math>.
''Binomiální halda'' reprezentující <math> S\,\!</math> je seznam stromů <math> T_i\,\!</math> takový, že celkový počet vrcholů v těchto stromech je <math> |S|\,\!</math> a je dáno jednoznačné přiřazení prvků vrcholům, respektující podmínku haldy. Každý strom je přitom izomorfní s nějakým <math> H_i\,\!</math> a dva <math> T_i,T_j, i\neq j\,\!</math> nejsou izomorfní.
Existence binomiální haldy pro každé přirozené <math> |S|\,\!</math> plyne z existence dvojkového zápisu čísla.
====Operace====
Operace na binomiálních haldách jsou založené na MERGE.
* '''MERGE''' 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í stromy stejného řádu, přenáší výsledky do dalšího spojování (přenos + obě haldy mající strom daného řádu = vyplivnutí 1 stromu na výsledek a spojení zbývajících dvou).
* '''INSERT''' je MERGE s jednoprvkovou haldou.
* '''MIN''' je projití kořenů a vypsání nejmenšího.
* '''DELETEMIN''' je '''MIN''', odebrání stromu s nejmenším prvkem v kořeni a přidání ('''MERGE''') podstromů jeho kořene do haldy.
* '''INCREASE''' a '''DECREASE''' se dělají úplně stejně jako u regulárních hald.
* Přímo není podporováno '''DELETE''', jen jako '''DECREASE''' + '''DELETEMIN'''.
* '''MAKEHEAP''' se provádí opakováním '''INSERT'''.
Složitost '''MERGE''' je <math> O(\log|S_1|+\log|S_2|)\,\!</math>, protože 1 krok '''SPOJ''' je konstantní. Halda má nejvýše <math> \log|S|\,\!</math> stromů, takže '''MIN''' a '''DELETEMIN''' mají tuto složitost. Výška všech stromů je <math> \leq\log|S|\,\!</math>, což dává složitost '''INCREASE''' <math> O(\log^2|S|)\,\!</math> a '''DECREASE''' <math> O(\log|S|)\,\!</math>. Pro odhad složitosti '''MAKEHEAP''' se použije amortizovaná složitost přičítání jedničky k binárnímu číslu, což je <math> O(1)\,\!</math>, tedy celkem <math> O(|S|)\,\!</math>.
====Líná implementace====
Vynecháme předpoklad neexistence dvou izomorfních stromů v haldě a budeme "vyvažování" provádět jen u operací '''MIN''' a '''DELETEMIN''', kdy se stejně musí projít všechny stromy. '''MERGE''' je pak prosté slepení seznamů hald. Vyvažování se provádí operací '''VYVAZ''', která sloučí izomorfní stromy (podobně jako '''MERGE''' z pilné implementace).
Složitost '''INSERT''' a '''MERGE''' je <math> O(1)\,\!</math>, ale '''DELETEMIN''' a '''MIN''' v nejhorším případě <math> O(|S|)\,\!</math>.
Amortizovaná složitost vychází ale líp: použijeme [[St%C3%A1tnice_-_Odhady_slo%C5%BEitosti#Algoritmus_.28Potenci.C3.A1lov.C3.A1_metoda.29|potenciálovou metodu]], když za hodnocení konfigurace <math>w(H)\,\;</math> zvolíme počet stromů v haldě <math>|\mathcal{H}|\,\!</math>. '''INSERT''' a '''MERGE''' ho nemění, resp. mění o <math> 1\,\!</math>, takže jsou stále <math> O(1)\,\!</math>.
Operace '''VYVAZ''' potřebuje <math> O(|H|)\,\!</math>, protože slití dvou stromů trvá konstantně dlouho a nelze slévat víc stromů, než kolik jich je v haldě. Kromě operace '''VYVAZ''' potřebuje '''MIN''' <math> O(|\mathcal{H}|)\,\!</math> a '''DELETEMIN''' <math> O(|\mathcal{H}|+\log|S|)\,\!</math> (max. stupeň stromu je logaritmický).
Dohromady vychází amortizovaná složitost pro '''MIN''': <math>am(o) = t(o) - w(H) + w(H') = O(|\mathcal{H}|-|\mathcal{H}|+\log|S|)\,\!</math>, protože výsledný počet stromů <math>|H'|\,\;</math> odpovídá pilné implementaci. Pro '''DELETEMIN''' podobně dostanu <math> O(|\mathcal{H}|+\log|S|-|\mathcal{H}|+\log|S|)=O(\log|S|)\,\!</math>.
===Fibonacciho haldy===
Definují se jako množiny stromů, které splňují podmínku haldy a ''musely vzniknout posloupností operací z prázdné haldy''. Všechny operace zachovávají podmínku, že jednomu vrcholu lze odříznout max. dva syny. Strom má ''rank'' <math> i\,\!</math>, má-li jeho kořen <math> i\,\!</math> synů (podobné jako izomorfismus s <math> H_i\,\!</math> u binomiálních hald).
Podmínka odříznutí max. dvou synů se zachovává pomocnou operací '''VYVAZ2'''. Když vrchol není kořen a byl mu předtím někdy odříznut syn, je speciálně označený. '''VYVAZ2''' 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. Když se vrchol stane kořenem, označení se zapomene.
====Operace====
'''MERGE, INSERT, MIN''' a '''DELETEMIN''' jsou stejné jako v líné implementaci binomiálních hald, jen požadavek na isomorfismus s <math> H_i\,\!</math> je nahrazen požadavkem na daný rank. Pomocné operace z binomiálních hald '''VYVAZ''' a '''SPOJ''' jsou také stejné.
'''DECREASE, INCREASE''' a '''DELETE''' vycházejí z leftist hald. Používají pomocnou operaci '''VYVAZ2'''
* '''DECREASE''' 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, na odtržené místo zavolá '''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.
====Korektnost a složitost====
Operace '''SPOJ''' podobně jako u binomiálních hald vyrobí ze dvou stromů ranku <math> i\,\!</math> jeden strom ranku <math> i+1\,\!</math>. Operace '''VYVAZ2''' zajistí, že od každého vrcholu kromě kořenů byl odtržen max. 1 syn -- když odtrhnu dalšího, odtrhu i tento vrchol a propaguju operaci nahoru.
Složitost operací:
* '''MERGE''' a '''INSERT''' je <math> O(1)\,\!</math> (stejně jako u binomiálních hald)
* '''MIN''' má <math> O(|\mathcal{H}|)\,\!</math> (nemění označení vrcholů)
* '''DELETEMIN''' <math> O(|\mathcal{H}|+\mathrm{maxrank}(\mathcal{H}))\,\!</math>, kde <math> maxrank\,\!</math> udává maximální rank stromu v haldě (může navíc odznačit některé vrcholy)
* '''DECREASE''' je <math> O(1+c)\,\!</math>, kde <math> c\,\!</math> je počet odznačených vrcholů (navíc označí max. 1 vrchol)
* '''INCREASE''' a '''DELETE''' jsou <math> O(1+c+d)\,\!</math>, kde navíc <math> d\,\!</math> je počet synů zvedaného nebo odstraňovaného vrcholu (také označí navíc max. 1 vrchol).
Pro výpočet amortizované složitosti použijeme potenciálovou metodu a zvolíme hodnotící funkci <math> w\,\!</math> jako počet stromů v haldě + <math> 2\times\,\!</math> počet označených vrcholů. Můžeme říct, že amortizovaná složitost '''MERGE''', '''INSERT''' a '''DECREASE''' je <math> O(1)\,\!</math>.
Označme max. rank stromů v lib. haldě reprezentující <math> n\,\!</math>-prvkovou množinu jako <math> \rho(n)\,\!</math>. Amortizovaná složitost '''MIN''', '''DELETEMIN''', '''INCREASE''' a '''DELETE''' pak je <math> O(\rho(n))\,\!</math> (pro '''MIN''' a '''DELETEMIN''' je vzorec amortizované složitosti podobný jako u binomiálních hald, pro '''INCREASE''' a '''DELETE''' je to vidět přímo ze vzorců).
Pro odhad <math>\rho(n)\,\;</math> je potřeba znát fakt, že <math> i\,\!</math>-tý nejstarší syn libovolného vrcholu má aspoň <math> i-2\,\!</math> synů (plyne z toho, že se slévají jen stromy stejného řádu a odtrhnout lze max. jednoho syna).
Vezmeme tedy nejmenší strom <math>T_j\,\;</math> ranku <math>j\,\;</math>, který toto splňuje. Ten musí být složením <math>T_{j-1}\,\;</math> a <math>T_{j-2}\,\;</math> (vzniká tak, že se slijí dva <math>T_{j-1}\,\;</math> a potom se na tom, který je pověšený jako syn nového kořenu, provede '''DECREASE''' a tím se z něj stane <math>T_{j-2}\,\;</math>). Z minimálního počtu synů se dá odvodit i rekurence <math>|T_k| \geq 1 + 1 + |T_0| + \dots + |T_{k-2}|</math>, která dá indukcí to samé.
Potom <math>|T_{k+1}| = F_k</math>, kde <math>F_k</math> je <math>k</math>-té Fibonacciho číslo. Pro Fibonacciho čísla platí, že <math>\lim_{k\to\infty} F_k = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^k</math>. Proto je <math>\rho(n) = O(\log(n))\,\;</math>, což dává logaritmickou amortizovanou složitost pro '''MIN''', '''DELETEMIN''', '''INCREASE''' a '''DELETE'''. Z toho pochází i název ''Fibonacciho'' haldy.
====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.
