Fibonaccijeva kopica

Iz MaFiRaWiki

(Razlika med različicami)

Različica od 13:37, 28 april 2007

Vsebina

Fibonaccijeva kopica

Fibonaccijeva kopica je kopica, sestavljena iz dreves z lastnostjo minimalnih kopic (angl. min-heap-ordered trees), kar pomeni da so spodnja vozlišča (otroci) v drevesu, vedno večja ali enaka od zgornjih vozlišč (staršev). Tako je tudi minimalni element v drevesu vedno na vrhu drevesa (eden od korenov). Kazalec na najmanjši element omogoča enostavno in hitro iskanje najmanjšega elementa. Fibonaccijeve kopice so podobne binomskim, vendar nimajo predpisane strukture oziroma niso urejena.

image:PrimerFibonacci.jpg
Slika 1.1 Primer Fibonaccijeve kopice.

Naslednja slika kaže, da so vsi vozli na istem nivoju (vozli, ki imajo istega očeta) povezani dvosmerno in ciklično. Koreni dreves so prav tako povezani dvosmerno in ciklično.

image:PrimerFibonacci2.jpg
Slika 1.2

Zasluge za nastanek Fibonaccijevih kopic imata Michael L. Fredman in Robert E. Tarjan. To je bilo leta 1984. Prvič se je o Fibonaccijevih kopicah pisalo leta 1987.

Fibonaccijeve kopice so dobile ime zaradi Fibonaccijevih števil, ki se uporabljajo v časovni analizi operacij.

Osnovne operacije na Fibonaccijevi kopici so:

  • vstavljanje novega drevesa (Insert),
  • brisanje minimalnega elementa (DeleteMin),
  • zmanjšanje ključa (DecreaseKey),
  • združitev dveh kopic (Union, merge),
  • iskanje minimalnega elementa (FindMinimum).


Pomoč pri razlagi psevdo kode:

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

Operacija Insert

Postopek:
Operacija Insert 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.

Operacija FindMinimum

Postopek:
Operacija MinRoot ali FindMinimum je trivialna, saj že imamo kazalec na najmanjši element v drevesu.

image:FindMin.jpg
Slika 1.3. Minimum kopice.

Psevdo koda:

 Fibonacci-Heap-Minimum(H)
 return min[H]

Operacija DeleteMin

Postopek:
Operacija deleteMin (ali ExtractMin) 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.

Operacija DecreaseKey

Postopek:
Operacija decreaseKey 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.

Operacija Union

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:

 Fibonacci-Heap-Union(H1,H2)
 H := Make-Fibonacci-Heap()
 min[H] := min[H1]
 Concatenate the root list of H2 with the root list of H 
 if (min[H1] = NIL) or (min[H2] <> NIL and min[H2] < min[H1])
 then min[H] := min[H2]
 n[H] := n[H1] + n[H2]
 free the objects H1 and H2
 return H


Uporaba Fibonaccijevih kopic

Fibonaccijeve kopice so minimalno vpeta drevesa. Z uporabo Fibonaccijevih kopic izboljšamo delovanje Dijkstrovega algoritma za iskanje najkrajših poti v grafih in Primovega algoritma za iskanje najcenejšega vpetega drevesa v grafu.

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