Фибоначи хип

У компјутерским наукама, Фибоначи хип као структура података хип,која се састоји од колекција стабала. Има боље амортизовано време (погедај Амортизована анализа) извршавања него биномни хип.Фибоначи хипове су развили Мицхаел L. Фредман и Роберт Е 1984 и први пут објавили у научном магазину 1987. Име Фибоначи хип долази од Фибоначијевих бројева (поглеедај: фибоначијев низ),који су се користили у анализи времена извршавања.

Операција наћи минимум ради у О(1) амортизованог времена.Операције убацити,смањи кључ и састави је имају константно амортизовано време извршавања. Операције брисање и брисање минимума ради у О(лог н) амортизованог времена. Ово значи да ће почевши од празне структуре података,нека секвенца од а операција из прве групе и б операција из друге групе би узела О(а + б лог н) времена. У Биномном хипу таква секвенца оберација би узела О((а + б) лог (н)). Фибоначи хип је тако бољи од Биномног хипа када је б асимптотски мање од а.

Коришћење Фибоначи хипова за редове са приоритетом побољшава асимптотско време извршавања битних алгоритама,као што су Дијкстра алгоритам за израчунавање најкраћег пута измедју два чвора у графу.

Структура

Фибоначи хип је колекција стабала која задовољава особину мин-хип,тј да кључ детета је увек већи или једнак кључевима родитеља. Ово подразумева да је најмањи кључ увек у корену једног од стабала.У поредјењу са биномиалним хипом,структура Фибоначи хипа је флексибилнија. Стабла немају прописани облик и у екстремном случају хип може имати сваки елемент у одвојеном дрвету.Ова флксибилност омогућава да буду извршене неке операције у "лењом" маниру,одлажући рад за неке касније операције.На пример састављање хипова је урадњено једноставно спајањем две листе стабала и операција смањивања кључа некада одсече чвор од његовог родиеља и формира ново дрво. Медјутим у неком моменту неки ред мора бити уведен у ред да би се постигло жењено време извршавања.У ствари,степени чврова(овде степен значи број деце) треба да остану поприлично ниски: сваки чвор има степен највише О(лог н) и величина подстабла којем је корен у чвору степена к је најмање Фк + 2,где је Фк к-ти Фибоначијев број. Ово је постигнуто правилом да можемо исећи највише једно дете сваког чвора који није корен. Када исечемо друго дете,сам чвор мора бити одсечен од свог родитеља и постаје корен новог стабла (погледати доказ степена граница,испод). Број стабала се смањује у перацији обриши минимум,где су стабла повезана.

Као резултат опуштене структуре, неке операције могу узети доста времена док су руге завршене веома брзо. За анализу амортизованог времена извршавања користимо потенцијални метод, у коме се претварамо да та веома брзе операције одузимају више времена него штозаиста узимају. Ово додатно време је касније спојено и одузето од праог времена извршавања спорих операција. Количина времена сачувана за каснију употребу може да се измери у сваком моменту потенцијалном функцијом. Потенцијал Фибоначијевог хипа је дат формулом:

потенцијал = т + 2м

где је т број стабала у Фибоначи хипу, а м је број маркираних чворова. А чвор је маркиран ако је бар од његове деце је исечен од када је чвор постао дете другог чвора (ниједан корен није маркиран). Амортизовано време за операцију је дато као сума реалног времена и ц помноженог са разликом у потенцијалу, где је ц константа (изабрана да одговара константном фактору у О нотацији за реално време).

Према томе, корен сваког стабла у хипу има једну јединицу времена сачувану. Ова јединица времена може бити коришћена касније да повеже ово стабло са другим у амортизованом времену 0. Такође, сваки маркиран чвор има две јединице времена сачуване. Једна може бити кориштена да одсече чвор од његовог родитеља. Уколико се ово догоди, чвор постаје корен и друга јединица времена ће остати сачувана у њему као у сваом другом корену.

Имплементација операција

Да би брисање и спајање било брзо,корени свих стабала у повезани помоћу кружне, двоструко-повезане листе. Деца сваког чвора су такоће повезана користећи такву листу. За сваки чвор, ми чувамо број његове деце и да ли је чвор означен. Штавише, ми чувамо показивач на корен помоћу најмањег корена.

Операција наћи минимум је сада тривијална зато што ми чувамо показивач на чвор који га садржи. Не мења потенцијал хипа, стога су и реална и амортизована цена константне. Као што је поменуто раније, спајање се имплементира једноставно спајањем листа корена стабала два хипа. Ово може бити урађено у константном времену и потенцијал се не мења, водећи поново до константног амортизованог времена. Операција уметања ради тако што се направи нови хип са једним елементом и извршаа спајање. За ово треба константно време, и потенцијал расте за један, зато што број стабала расте. Амортизована цена је због тога остаје константна.

Операција екстрахуј минимум (исто као избриши минимум) ради у три фазе. Прво узмемо корен који садржи минимални елемент и избацимо га. Његова деца ће постати корење нових стабала. Ако је број деце био д, потребно је О(д) времена да обради сво ново корење и потонцијал се повећава за д-1. Стога амортизовано текуће време ове фазе је О(д) = О(лог н). Међутим да би се довршило брисање минимума, морамо ажурирати показивач на корен са минималим кључем. Нажалост може бити до н корена које морамо проверити. У другој фази ми стога смањујемо број корена успешно повезујући корење истог степена.Када два корена у и в имају исти степен,ми узмемо да је онај са већим кључем дете,а овај са мањим корен. Степен ће да се повећа за један. Ово се понавља док сваки корен нема различите степене. Да би нашли стабла истог степена ефикасно,користимо низ у којем му чувамо показивач на један корен сваког степена. Када надјемо други корен истог степена, повежемо их и ажурирамо низ. Реално ввреме извршавања је О(лог н + м) где је м број корена на почетку друге фазе. На крају ћемо имати највише О(лог н) корена(зато што сваки има други степен). Стога разлика у потенцијалима пре и после ове фазе је: О(лог н) − м , а амортизовано време извршавања је највише О(лог н + м) + ц(О(лог н) − м). Уз избор довољно великог ц, ово поједностављује то на О(лог н).

Операција смањење кључа ће узети чвор, смањити кључ и ако особина хипа постане нарушена (нови кључ је мањи од кључа родитеља), чвор се одсеца од родитеља. Ако родитељ није корен, онда је означен. Ако је већ означен, сече се као и означени родитељ. Настављамо нагоре док не достигнемо или корен или необележен чвор. У процесу креирамо неки број, на пример к, нових стабала. Сваки од ових нових стабала ,осим можда првог, оригинално означеног али као корен, ће постати неозначен. Један чвор може постати обележен. Стога, број обележених чворова се мења за −(к − 1) + 1 = − к + 2. Комбинујући ове две промене, потенцијална промена је за 2(−к + 2) + к = −к +4. Реално време за извршавање сечења је О(к), стога (опет са довољно великим избором ц) амортизовано текуће време је константно. Коначно, операција брисања се може једноставно имплементирати смањењем кључа елемента који треба да се брише до минус бесконачно, тако га претварајући у минимум целог хипа. Онда бирамо минимум и избацујемо га. Амортизовано текуће време ове операције је О(лог н).

Доказ степена граница

Амортизована перформанса Фибоначи хипа зависи од степена ( броја деце ) било ког корена стабла и она је О(лог н), где је н веичина хипа. Овде показујемо да је величина (под)стабла са кореном у било ком чвору x степена д у хипу бар Ф_д+2 , где је Ф_к к-ти Фибоначијев број. Степен долази од овога и чињенице да $F_{d+2}\geq \varphi ^{d}$ за све интегере $d\geq 0$, где $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$. (Онда имамо $n\geq \varphi ^{d}$, и стављајући лог у базу $\varphi$ обе стране даје $d\leq \log _{\varphi }n$ као што је тражено. Сматрамо било који чвор x негде у хипу ( x не треба да буде корен неког од главних стабала ). Дефинишемо величину(x) као величину дрвета коме је корен x (број потомака од x,укључујући и њега самог). Доказујемо индукцијом по висини од x (дужина најдуже једноставне путање од x до листа потомка), где величина(x) ≥ Ф_д+2, где је д сстепен од x. Базни случај: Ако xима висину 0,онда д = 0, и висина(x) = 1 = Ф₂. Индуктивна хипотеза: Претпоставимо да x има позитивну висину и степен д>0. Ставимо y₁, y₂, ..., y_д да буду деца од x,индексирана у поретку времена када су најскорије били деца од x ( y₁ је први и y_д је последњи), и ставимо ц₁, ц₂, ..., ц_д да буду њихови степени редом. Ми тврдимо да ц_и ≥ и-2 за сваки и са 2≤и≤д: стачно пре y_и је постао дете од x,y₁,...,y_и−1 су већ били деца од x, и тако x је имао степен најмање и−1 у том тренутку. Како се стабла спајају само када су им степени корена једнаки, мора да је y_и такодје имао степен најмање и-1 у тренутку када је постао дете од x. Од тог тренутка до сада, y_и је једино могао да изгуби једно дете (како је гарантовано у процесу маркирања), и тако је његов тренутни степен ц_и је најмање и−2.Овим смо потврдили тврдњу са почетка. Како су висине свих y_и стриктно мање од x, можемо применити индуктивну хипотезу на њих да би добили величину(y_и) ≥ Ф_ци+2 ≥ Ф_(и−2)+2 = Ф_и. Чворови x и y₁ доприносе најмање 1 величини(x), и онда имамо

${\textbf {size}}(x)\geq 2+\sum _{i=2}^{d}{\textbf {size}}(y_{i})\geq 2+\sum _{i=2}^{d}F_{i}=1+\sum _{i=0}^{d}F_{i}.$

Рутинска индукција доказује да $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ за било који $d\geq 0$,који даје жељену нижу границу за величину(x).

Најгори случај

Иако је тотално време извршавања секвенце операција која почиње празном структуром омедјена границама датим горе,неке (врло мало) операција у секвенци могу се извршавати јако дуго (на пример брисање и брисање минимума имају линеарно време извршавања у најгорем случају). Зато Фибоначи хипови и друге амортизоване структуре података нису погодне за системе који раде у реалном времену. Могуће је направити структуре података које имају исти најгори случај као Фибоначи има амортизован случај. Медјутим,добијена структура (Бродал ред) је,по речима самог креатора",доста компликована" и "не применљива у пракси".

Сума времена извршасавања

Операција	Ефекат	Несортирана повезана листа	Сортирана повезана листа	Самобалансирајуће бинарно стабло претраге	Бинарни хип	Биномни хип	Фибоначи хип	Бродал ред	Паиринг хип
убаци(податак,кључ)	Додаје "податак" у ред,тагован са "кључ"	О(1)	О(н)	О(лог н)	О(лог н)	О(лог н)	О(1)	О(1)	О(1)
надјиМин() -> кљуц,податак	Враћа "кључ,податак" која одговара минималној вредности "кључа"	О(н)	О(1)	О(лог н) ор О(1) (**)	О(1)	О(лог н) ор О(1) (**)	О(1)	О(1)	О(1)
обришиМин()	Брише "податак" који одговара минималној вредности "кјуча"	О(н)	О(1)	О(лог н)	О(лог н)	О(лог н)	О(лог н)*	О(лог н)	О(лог н)*
обриши(чвор)	Брисе "податак" који одговара датом "кључу"	О(1)	О(1)	О(лог н)	О(лог н)	О(лог н)	О(лог н)*	О(лог н)	О(лог н)*
самњиКључ(чвор)	смањује "кључ" чвора,дат је показивач чвора који треба модификовати	О(1)	О(н)	О(лог н)	О(лог н)	О(лог н)	О(1)*	О(1)	Ункноwн бут боундед: $\Omega (\log \log n),{O(2^{2{\sqrt {\log \log n}}})}$*
споји(хип1,хип2) -> хип3	Спаја два хипа у трећи	О(1)	О(м + н)	О(м лог(н+м))	О(м лог(н+м))	О(лог (м+н))	О(1)*	О(1)	О(1)

(*)Амортизовано време

(**)Са тривијалном модификацијом да сачува додатни показивач на минимални елемент