Fibonaccijeva kopica

Iz MaFiRaWiki

Fibonaccijeva kopica (Michael L. Fredman in Robert E. Tarjan, 1984) je podatkovna struktura, ki se uporablja za predtavitev vrste s prednostjo. Z uporabo Fibonaccijevih kopic želimo minimizirati število operacij pri iskanju najkrajše poti v grafu (Dijkstrov algoritem) in najcenejšega vpetega drevesa v grafu (Primov algoritem).

Način, s katerim želimo minimizirati število operacij, je lenoba: delaj toliko, kolikor je potrebno in to naredi tako, da strukturo poenostaviš kolikor se le da, da si potem olajšaš nadaljnje delo. Na ta način je uporabnik primoran narediti več enostavnih operacij, da bi podatkovna struktura zgledala bolj zakomplicirana.

Fibonaccijeve kopice so sestavljene iz dreves, ki imajo kopično lastnost. Taka drevesa imajo to lastnost, da velja

ključ (oče) <= ključ (sin)

za vsa vozlišča v drevesu.

Fibonaccijeva kopica je zbirka dreves z naslednjimi lastnostmi:
1. Koreni dreves so povezani dvosmerno in ciklično (seznam korenov v kopici H).
2. Koren vsakega drevesa vsebuje minimalni element (to sledi iz tega, da ima drevo lastnost minimalne kopice).
3. Do kopice dostopamo preko korena, ki vsebuje minimalni element.
4. Za vsako vozlišče x beležimo njegovo stopnjo, ki je enaka številu otrok, ki jih x ima. Beležimo tudi,ali je vozlišče označeno ali ni. Tu ima x vrednost true (je označeno) ali false (ni označeno). Koren ni nikoli označen. Označimo tisto vozlišče, ki ni koren in ki je izgubilo otroka (eden od otrok je bil odrezan in postavljen med korene). Vozlišče odznačimo, ko postane koren.

Vsi vozli na istem nivoju (vozli, ki imajo istega očeta) so povezani dvosmerno in ciklično.

image:FibonacciPrimer.jpg

Slika 1.1 Podroben prikaz Fibonaccijeve kopice.

V primerjavi z binomsko kopico, je struktura Fibonaccijeve kopice bolj fleksibilna. Čeprav so drevesa v Fibonaccijevi kopici neurejena, je enkrat treba uvesti red, da dosežemo optimalni čas izvajanja operacij. V splošnem je stopnja vozlišč nizka: vsako vozlišče je lahko stopnje največ O(log n) in velikost drevesa pod vozliščem k-te stopnje je vsaj Fk+2, kjer je Fk k-to Fibonaccijevo število (od tod ime Fibonaccijeva kopica). To je zaradi pravila, da lahko odstranimo vselej največ enega otroka vozlišču, ki pa ne sme biti koren. Če odstranimo še drugega otroka, potem vozlišče postane koren novega drevesa.

Zaradi take strukture se lahko nekatere operacije izvajajo dalj časa kot nekatere, ki se izvedejo zelo hitro. V časovni analizi za nekatere hitre operacije predvidevamo, da rabijo malo več časa, kot ga v resnici rabijo. Ta dodatni čas je kasneje odvzet od aktualnega časa počasnejših operacij. Količino shranjenega časa za nadaljnjo uporabo v katerem koli trenutku merimo s potencialno funkcijo. Potencial Fibonaccijeve kopice izračunamo z naslednjo formulo:

Potencial = t + 2m,

kjer je t število dreves v Fibonaccijevi kopici in m je število označenih vozlišč.

image:PrimerFibonaccijevaKopica.jpg

Slika 1.2 Ta Fibonaccijeva kopica je sestavljena iz petih dreves (minimalnih kopic) in 14 vozlišč.
Črtkana črta označuje korene dreves. Minimalni element drevesa je vozlišče s ključem 3.
Potencial te Fibonaccijeve kopice je 5 + 2*3 = 11.

Koren vsakega drevesa v kopici ima shranjeno eno časovno enoto. Ta enota se lahko kasneje uporabi, da povežemo skupaj dve drevesi. Vsako označeno vozlišče ima shranjeno dve časovni enoti. Ena enota se lahko porabi, ko odcepimo vozlišče od starša. Če se to zgodi, vozlišče postane koren in druga časovna enota ostane shranjena kot pri vseh ostalih korenih.

Vsebina

Operacije na Fibonaccijevih kopicah

Operacije, ki jih izvajamo na Fibonaccijevi kopici so naslednje:

  • vstavljanje novega drevesa,
  • iskanje minimalnega elementa,
  • zmanjšanje ključa v drevesu,
  • unija dveh kopic,
  • brisanje minimuma.


Operacije vstavljanje, iskanje minimuma, zmanjšanje ključa in unija dveh kopic se izvedeju v času O(1). Edini požrešnejši operaciji sta brisanje minimuma in zmanjšanje ključa, ki potrebujeta O(log n) časa.

Razlaga psevdo kode:

 n[H] .... število vozlišč v drevesu H,
 min[H] .... minimum drevesa H, 
 stopnja[x] .... stopnja drevesa x, 
 p[x] .... starš od x, 
 otrok[x] .... otrok od x,
 levi[x] .... levi otrok od x,
 desni[x] .... desni otrok od x,
 mark[x] .... označeno vozlišče od x,
 ključ[x] .... ključ vozlišča x.


Vstavljanje


Postopek:
Operacija vstavi deluje tako, da za vsak element,ki ga vstavljamo v kopico, naredimo novo drevo z enim samim elementom in to drevo dodamo na levo stran najmanjšega elementa. Če je potrebno popravimo kazalec na najmanjši element.


Poišči minimum


Postopek:
Operacija iskanje minimuma je trivialna, saj že imamo kazalec na najmanjši element v drevesu.

image:FindMin.jpg

Slika 1.3. Minimum kopice.

Psevdo koda:

 Fibonaccijeva-Kopica-Minimum(H)
 return min[H]


Zbriši minimum


Postopek:
Operacija zbriši minimum deluje v treh fazah. Najprej poiščemo koren, ki vsebuje najmanjši element (min) in ga odstranimo. Njegovi otroci postanejo koreni novega drevesa. Če bi bilo d otrok, bi nam vzelo O(d) časa za nastanek novih korenov in potencial bi narasel za d-1. Zato je časovna kompleknost te faze O(d)=O(log n).
Naslednja stvar, ki jo moramo narediti je, da poiščemo koren z najmanjšim elementom (poiščemo nov min). To naredimo tako, da zmanjšamo število korenov s tem da združimo tiste z isto stopnjo. Torej če imamo koren u in v z isto stopnjo, postane tisti z manjšim elementom koren (starš) tistemu z večjim elementom. Stopnja se bo povečala za ena. To ponavljamo toliko časa, dokler nima vsak koren različne stopnje. V tretji fazi preverimo korene in poiščemo minimum.


Zmanjšanje ključa


Postopek:
Operacija zmanjšaj ključ deluje tako, da najprej izberemo ključ, ki ga želimo zmanjšati, ga zmanjšamo in če se lastnosti kopice spremenijo (nov ključ je manjši kot ključ starša), se vozlišče odcepi od starša. Če starš ni koren, ga označimo (pobarvamo s črno). Če pa je bil že prej označen, ga prav tako odcepimo in označimo njegovega starša. Nadaljujemo na tak način, vse dokler ne pridemo do korena ali pa do neoznačenega vozlišča. Odcepljena vozlišča postanejo koreni drevesa.


Unija dveh kopic


Postopek:
Operacija unije primerja dva najmanjša elementa kopic, ki ju želimo združiti. Kopica z večjim elementom postane levi sosed kopice z manjšim elementom. Pobrišemo stare povezave in naredimo nove.

Primer:

image:Union1.jpg

Slika 1.4 Imamo dve Fibonaccijevi kopici, ki ju bomo združili.

image:Union2.jpg

Slika 1.5 Nastala je ena Fibonaccijeva kopica. Čas potreben za to je O(1).

Psevdo koda:

 Fibonaccijeva-Kopica-Unija(H1,H2)
 H := Naredi-Fibonaccijevo-Kopico()
 min[H] := min[H1]  
 if (min[H1] = null) || (min[H2] ≠ null && min[H2] < min[H1])
 then min[H] := min[H2]
 n[H] := n[H1] + n[H2]  
 return H

Glej tudi

Viri

Literatura

  • Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introductions to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 20: Fibonacci Heaps, pp. 476-497.
Osebna orodja