Fibonači hip

U kompjuterskim naukama, Fibonači hip kao struktura podataka hip,koja se sastoji od kolekcija stabala. Ima bolje amortizovano vreme (pogedaj Amortizovana analiza) izvršavanja nego binomni hip.Fibonači hipove su razvili Michael L. Fredman i Robert E 1984 i prvi put objavili u naučnom magazinu 1987. Ime Fibonači hip dolazi od Fibonačijevih brojeva (pogleedaj: fibonačijev niz),koji su se koristili u analizi vremena izvršavanja.

Operacija naći minimum radi u O(1) amortizovanog vremena.Operacije ubaciti,smanji ključ i sastavi je imaju konstantno amortizovano vreme izvršavanja. Operacije brisanje i brisanje minimuma radi u O(log n) amortizovanog vremena. Ovo znači da će počevši od prazne strukture podataka,neka sekvenca od a operacija iz prve grupe i b operacija iz druge grupe bi uzela O(a + b log n) vremena. U Binomnom hipu takva sekvenca oberacija bi uzela O((a + b) log (n)). Fibonači hip je tako bolji od Binomnog hipa kada je b asimptotski manje od a.

Korišćenje Fibonači hipova za redove sa prioritetom poboljšava asimptotsko vreme izvršavanja bitnih algoritama,kao što su Dijkstra algoritam za izračunavanje najkraćeg puta izmedju dva čvora u grafu.

Struktura

Fibonači hip je kolekcija stabala koja zadovoljava osobinu min-hip,tj da ključ deteta je uvek veći ili jednak ključevima roditelja. Ovo podrazumeva da je najmanji ključ uvek u korenu jednog od stabala.U poredjenju sa binomialnim hipom,struktura Fibonači hipa je fleksibilnija. Stabla nemaju propisani oblik i u ekstremnom slučaju hip može imati svaki element u odvojenom drvetu.Ova flksibilnost omogućava da budu izvršene neke operacije u "lenjom" maniru,odlažući rad za neke kasnije operacije.Na primer sastavljanje hipova je uradnjeno jednostavno spajanjem dve liste stabala i operacija smanjivanja ključa nekada odseče čvor od njegovog rodielja i formira novo drvo. Medjutim u nekom momentu neki red mora biti uveden u red da bi se postiglo ženjeno vreme izvršavanja.U stvari,stepeni čvrova(ovde stepen znači broj dece) treba da ostanu poprilično niski: svaki čvor ima stepen najviše O(log n) i veličina podstabla kojem je koren u čvoru stepena k je najmanje Fk + 2,gde je Fk k-ti Fibonačijev broj. Ovo je postignuto pravilom da možemo iseći najviše jedno dete svakog čvora koji nije koren. Kada isečemo drugo dete,sam čvor mora biti odsečen od svog roditelja i postaje koren novog stabla (pogledati dokaz stepena granica,ispod). Broj stabala se smanjuje u peraciji obriši minimum,gde su stabla povezana.

Kao rezultat opuštene strukture, neke operacije mogu uzeti dosta vremena dok su ruge završene veoma brzo. Za analizu amortizovanog vremena izvršavanja koristimo potencijalni metod, u kome se pretvaramo da ta veoma brze operacije oduzimaju više vremena nego štozaista uzimaju. Ovo dodatno vreme je kasnije spojeno i oduzeto od praog vremena izvršavanja sporih operacija. Količina vremena sačuvana za kasniju upotrebu može da se izmeri u svakom momentu potencijalnom funkcijom. Potencijal Fibonačijevog hipa je dat formulom:

potencijal = t + 2m

gde je t broj stabala u Fibonači hipu, a m je broj markiranih čvorova. A čvor je markiran ako je bar od njegove dece je isečen od kada je čvor postao dete drugog čvora (nijedan koren nije markiran). Amortizovano vreme za operaciju je dato kao suma realnog vremena i c pomnoženog sa razlikom u potencijalu, gde je c konstanta (izabrana da odgovara konstantnom faktoru u O notaciji za realno vreme).

Prema tome, koren svakog stabla u hipu ima jednu jedinicu vremena sačuvanu. Ova jedinica vremena može biti korišćena kasnije da poveže ovo stablo sa drugim u amortizovanom vremenu 0. Takođe, svaki markiran čvor ima dve jedinice vremena sačuvane. Jedna može biti korištena da odseče čvor od njegovog roditelja. Ukoliko se ovo dogodi, čvor postaje koren i druga jedinica vremena će ostati sačuvana u njemu kao u svaom drugom korenu.

Implementacija operacija

Da bi brisanje i spajanje bilo brzo,koreni svih stabala u povezani pomoću kružne, dvostruko-povezane liste. Deca svakog čvora su takoće povezana koristeći takvu listu. Za svaki čvor, mi čuvamo broj njegove dece i da li je čvor označen. Štaviše, mi čuvamo pokazivač na koren pomoću najmanjeg korena.

Operacija naći minimum je sada trivijalna zato što mi čuvamo pokazivač na čvor koji ga sadrži. Ne menja potencijal hipa, stoga su i realna i amortizovana cena konstantne. Kao što je pomenuto ranije, spajanje se implementira jednostavno spajanjem lista korena stabala dva hipa. Ovo može biti urađeno u konstantnom vremenu i potencijal se ne menja, vodeći ponovo do konstantnog amortizovanog vremena. Operacija umetanja radi tako što se napravi novi hip sa jednim elementom i izvršaa spajanje. Za ovo treba konstantno vreme, i potencijal raste za jedan, zato što broj stabala raste. Amortizovana cena je zbog toga ostaje konstantna.

Operacija ekstrahuj minimum (isto kao izbriši minimum) radi u tri faze. Prvo uzmemo koren koji sadrži minimalni element i izbacimo ga. Njegova deca će postati korenje novih stabala. Ako je broj dece bio d, potrebno je O(d) vremena da obradi svo novo korenje i potoncijal se povećava za d-1. Stoga amortizovano tekuće vreme ove faze je O(d) = O(log n). Međutim da bi se dovršilo brisanje minimuma, moramo ažurirati pokazivač na koren sa minimalim ključem. Nažalost može biti do n korena koje moramo proveriti. U drugoj fazi mi stoga smanjujemo broj korena uspešno povezujući korenje istog stepena.Kada dva korena u i v imaju isti stepen,mi uzmemo da je onaj sa većim ključem dete,a ovaj sa manjim koren. Stepen će da se poveća za jedan. Ovo se ponavlja dok svaki koren nema različite stepene. Da bi našli stabla istog stepena efikasno,koristimo niz u kojem mu čuvamo pokazivač na jedan koren svakog stepena. Kada nadjemo drugi koren istog stepena, povežemo ih i ažuriramo niz. Realno vvreme izvršavanja je O(log n + m) gde je m broj korena na početku druge faze. Na kraju ćemo imati najviše O(log n) korena(zato što svaki ima drugi stepen). Stoga razlika u potencijalima pre i posle ove faze je: O(log n) − m , a amortizovano vreme izvršavanja je najviše O(log n + m) + c(O(log n) − m). Uz izbor dovoljno velikog c, ovo pojednostavljuje to na O(log n).

Operacija smanjenje ključa će uzeti čvor, smanjiti ključ i ako osobina hipa postane narušena (novi ključ je manji od ključa roditelja), čvor se odseca od roditelja. Ako roditelj nije koren, onda je označen. Ako je već označen, seče se kao i označeni roditelj. Nastavljamo nagore dok ne dostignemo ili koren ili neobeležen čvor. U procesu kreiramo neki broj, na primer k, novih stabala. Svaki od ovih novih stabala ,osim možda prvog, originalno označenog ali kao koren, će postati neoznačen. Jedan čvor može postati obeležen. Stoga, broj obeleženih čvorova se menja za −(k − 1) + 1 = − k + 2. Kombinujući ove dve promene, potencijalna promena je za 2(−k + 2) + k = −k +4. Realno vreme za izvršavanje sečenja je O(k), stoga (opet sa dovoljno velikim izborom c) amortizovano tekuće vreme je konstantno. Konačno, operacija brisanja se može jednostavno implementirati smanjenjem ključa elementa koji treba da se briše do minus beskonačno, tako ga pretvarajući u minimum celog hipa. Onda biramo minimum i izbacujemo ga. Amortizovano tekuće vreme ove operacije je O(log n).

Dokaz stepena granica

Amortizovana performansa Fibonači hipa zavisi od stepena ( broja dece ) bilo kog korena stabla i ona je O(log n), gde je n veičina hipa. Ovde pokazujemo da je veličina (pod)stabla sa korenom u bilo kom čvoru x stepena d u hipu bar F_d+2 , gde je F_k k-ti Fibonačijev broj. Stepen dolazi od ovoga i činjenice da $F_{d+2}\geq \varphi ^{d}$ za sve integere $d\geq 0$, gde $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$. (Onda imamo $n\geq \varphi ^{d}$, i stavljajući log u bazu $\varphi$ obe strane daje $d\leq \log _{\varphi }n$ kao što je traženo. Smatramo bilo koji čvor x negde u hipu ( x ne treba da bude koren nekog od glavnih stabala ). Definišemo veličinu(x) kao veličinu drveta kome je koren x (broj potomaka od x,uključujući i njega samog). Dokazujemo indukcijom po visini od x (dužina najduže jednostavne putanje od x do lista potomka), gde veličina(x) ≥ F_d+2, gde je d sstepen od x. Bazni slučaj: Ako xima visinu 0,onda d = 0, i visina(x) = 1 = F₂. Induktivna hipoteza: Pretpostavimo da x ima pozitivnu visinu i stepen d>0. Stavimo y₁, y₂, ..., y_d da budu deca od x,indeksirana u poretku vremena kada su najskorije bili deca od x ( y₁ je prvi i y_d je poslednji), i stavimo c₁, c₂, ..., c_d da budu njihovi stepeni redom. Mi tvrdimo da c_i ≥ i-2 za svaki i sa 2≤i≤d: stačno pre y_i je postao dete od x,y₁,...,y_i−1 su već bili deca od x, i tako x je imao stepen najmanje i−1 u tom trenutku. Kako se stabla spajaju samo kada su im stepeni korena jednaki, mora da je y_i takodje imao stepen najmanje i-1 u trenutku kada je postao dete od x. Od tog trenutka do sada, y_i je jedino mogao da izgubi jedno dete (kako je garantovano u procesu markiranja), i tako je njegov trenutni stepen c_i je najmanje i−2.Ovim smo potvrdili tvrdnju sa početka. Kako su visine svih y_i striktno manje od x, možemo primeniti induktivnu hipotezu na njih da bi dobili veličinu(y_i) ≥ F_ci+2 ≥ F_(i−2)+2 = F_i. Čvorovi x i y₁ doprinose najmanje 1 veličini(x), i onda imamo

${\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}.$

Rutinska indukcija dokazuje da $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ za bilo koji $d\geq 0$,koji daje željenu nižu granicu za veličinu(x).

Najgori slučaj

Iako je totalno vreme izvršavanja sekvence operacija koja počinje praznom strukturom omedjena granicama datim gore,neke (vrlo malo) operacija u sekvenci mogu se izvršavati jako dugo (na primer brisanje i brisanje minimuma imaju linearno vreme izvršavanja u najgorem slučaju). Zato Fibonači hipovi i druge amortizovane strukture podataka nisu pogodne za sisteme koji rade u realnom vremenu. Moguće je napraviti strukture podataka koje imaju isti najgori slučaj kao Fibonači ima amortizovan slučaj. Medjutim,dobijena struktura (Brodal red) je,po rečima samog kreatora",dosta komplikovana" i "ne primenljiva u praksi".

Suma vremena izvršasavanja

Operacija	Efekat	Nesortirana povezana lista	Sortirana povezana lista	Samobalansirajuće binarno stablo pretrage	Binarni hip	Binomni hip	Fibonači hip	Brodal red	Pairing hip
ubaci(podatak,ključ)	Dodaje "podatak" u red,tagovan sa "ključ"	O(1)	O(n)	O(log n)	O(log n)	O(log n)	O(1)	O(1)	O(1)
nadjiMin() -> kljuc,podatak	Vraća "ključ,podatak" koja odgovara minimalnoj vrednosti "ključa"	O(n)	O(1)	O(log n) or O(1) (**)	O(1)	O(log n) or O(1) (**)	O(1)	O(1)	O(1)
obrišiMin()	Briše "podatak" koji odgovara minimalnoj vrednosti "kjuča"	O(n)	O(1)	O(log n)	O(log n)	O(log n)	O(log n)*	O(log n)	O(log n)*
obriši(čvor)	Brise "podatak" koji odgovara datom "ključu"	O(1)	O(1)	O(log n)	O(log n)	O(log n)	O(log n)*	O(log n)	O(log n)*
samnjiKljuč(čvor)	smanjuje "ključ" čvora,dat je pokazivač čvora koji treba modifikovati	O(1)	O(n)	O(log n)	O(log n)	O(log n)	O(1)*	O(1)	Unknown but bounded: $\Omega (\log \log n),{O(2^{2{\sqrt {\log \log n}}})}$*
spoji(hip1,hip2) -> hip3	Spaja dva hipa u treći	O(1)	O(m + n)	O(m log(n+m))	O(m log(n+m))	O(log (m+n))	O(1)*	O(1)	O(1)

(*)Amortizovano vreme

(**)Sa trivijalnom modifikacijom da sačuva dodatni pokazivač na minimalni element