Fibonaccijeva kopica

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 13:37, 28 april 2007
AleksandraVujasin (Pogovor | prispevki)

← Prejšnja različica
Različica od 18:38, 1 maj 2007
AleksandraVujasin (Pogovor | prispevki)

Naslednja različica →
Vrstica 3: Vrstica 3:
'''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 [[binomska kopica|binomskim]], vendar nimajo predpisane strukture oziroma niso urejena. '''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 [[binomska kopica|binomskim]], vendar nimajo predpisane strukture oziroma niso urejena.
-[[image:PrimerFibonacci.jpg]]<br>+<center>[[image:PrimerFibonacci.jpg]]</center><br>
-Slika 1.1 Primer Fibonaccijeve kopice.<br>+<center>Slika 1.1 Primer Fibonaccijeve kopice.</center><br>
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. 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]]<br>+<center>[[image:PrimerFibonacci2.jpg]]</center><br>
-Slika 1.2 <br>+<center>Slika 1.2 Shema povezav </center>
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. 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.
Vrstica 16: Vrstica 16:
Osnovne operacije na Fibonaccijevi kopici so: Osnovne operacije na Fibonaccijevi kopici so:
-* vstavljanje novega drevesa ('''Insert'''),+* vstavljanje novega drevesa,
-* brisanje minimalnega elementa ('''DeleteMin'''),+* brisanje minimalnega elementa,
-* zmanjšanje ključa ('''DecreaseKey'''),+* zmanjšanje ključa,
-* združitev dveh kopic ('''Union, merge'''),+* združitev dveh kopic,
-* iskanje minimalnega elementa ('''FindMinimum''').+* iskanje minimalnega elementa.
 +==Operacije na Fibonaccijevih kopicah==
-Pomoč pri razlagi '''psevdo kode''':+Razlaga '''psevdo kode''':
n[H] .... število vozlišč v drevesu H, n[H] .... število vozlišč v drevesu H,
min[H] .... minimum drevesa H, min[H] .... minimum drevesa H,
- degree[x] .... stopnja drevesa x, + stopnja[x] .... stopnja drevesa x,
p[x] .... starš od x, p[x] .... starš od x,
- child[x] .... otrok od x,+ otrok[x] .... otrok od x,
- left[x] .... levi otrok od x,+ levi[x] .... levi otrok od x,
- right[x] .... desni otrok od x,+ desni[x] .... desni otrok od x,
mark[x] .... označeno vozlišče od x, mark[x] .... označeno vozlišče od x,
- key[x] .... ključ vozlišča x.+ ključ[x] .... ključ vozlišča x.
-==Operacija Insert==+ 
 +===Vstavljanje===
 +<hr>
'''Postopek:'''<br> '''Postopek:'''<br>
-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.<br>+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.<br>
* [[/Primer vstavljanja drevesa|Primer]] * [[/Primer vstavljanja drevesa|Primer]]
-==Operacija FindMinimum==+ 
 +===Poišči minimum===
 +<hr>
'''Postopek:'''<br> '''Postopek:'''<br>
-Operacija MinRoot ali FindMinimum je trivialna, saj že imamo kazalec na najmanjši element v drevesu.+Operacija iskanje minimuma je trivialna, saj že imamo kazalec na najmanjši element v drevesu.
-[[image:FindMin.jpg]]<br>+<center>[[image:FindMin.jpg]]</center><br>
-Slika 1.3. Minimum kopice.<br>+<center>Slika 1.3. Minimum kopice.</center><br>
'''Psevdo koda''': '''Psevdo koda''':
Vrstica 52: Vrstica 57:
return min[H] return min[H]
-==Operacija DeleteMin==+ 
 +===Zbriši minimum===
 +<hr>
'''Postopek''':<br> '''Postopek''':<br>
-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).<br>+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).<br>
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. 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. V tretji fazi preverimo korene in poiščemo minimum.
Vrstica 61: Vrstica 68:
* [[/Primer brisanja minimuma|Primer]] * [[/Primer brisanja minimuma|Primer]]
-==Operacija DecreaseKey==+ 
 +===Zmanjšanje ključa===
 +<hr>
'''Postopek''':<br> '''Postopek''':<br>
-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 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.
* [[/Primer manjšanja ključa|Primer]] * [[/Primer manjšanja ključa|Primer]]
-==Operacija Union==+ 
 +===Unija dveh kopic===
 +<hr>
'''Postopek''':<br> '''Postopek''':<br>
Vrstica 75: Vrstica 86:
'''Primer''':<br> '''Primer''':<br>
-[[image:Union1.jpg]]<br>+<center>[[image:Union1.jpg]]</center><br>
-Slika 1.4 Imamo dve Fibonaccijevi kopici, ki ju bomo združili.<br>+<center>Slika 1.4 Imamo dve Fibonaccijevi kopici, ki ju bomo združili.</center><br>
-[[image:Union2.jpg]]<br>+<center>[[image:Union2.jpg]]</center><br>
-Slika 1.5 Nastala je ena Fibonaccijeva kopica. Čas potreben za to je O(1).<br>+<center>Slika 1.5 Nastala je ena Fibonaccijeva kopica. Čas potreben za to je O(1).</center><br>
'''Psevdo koda''': '''Psevdo koda''':
Fibonacci-Heap-Union(H1,H2) Fibonacci-Heap-Union(H1,H2)
H := Make-Fibonacci-Heap() H := Make-Fibonacci-Heap()
- min[H] := min[H1]+ 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])
- if (min[H1] = NIL) or (min[H2] <> NIL and min[H2] < min[H1])+
then min[H] := min[H2] then min[H] := min[H2]
- n[H] := n[H1] + n[H2]+ n[H] := n[H1] + n[H2]
- free the objects H1 and H2+
return H return H
- 
==Uporaba Fibonaccijevih kopic== ==Uporaba Fibonaccijevih kopic==
-Fibonaccijeve kopice so minimalno vpeta drevesa. Z uporabo Fibonaccijevih kopic izboljšamo delovanje [[Dijkstrov algoritem|Dijkstrovega algoritma]] za iskanje najkrajših poti v grafih in [[Primov algoritem|Primovega algoritma]] za iskanje najcenejšega vpetega drevesa v grafu.+Z uporabo Fibonaccijevih kopic izboljšamo delovanje [[Dijkstrov algoritem|Dijkstrovega algoritma]] za iskanje najkrajših poti v grafih in [[Primov algoritem|Primovega algoritma]] za iskanje najcenejšega vpetega drevesa v grafu.
==Glej tudi== ==Glej tudi==

Različica od 18:38, 1 maj 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 Shema povezav

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,
  • brisanje minimalnega elementa,
  • zmanjšanje ključa,
  • združitev dveh kopic,
  • iskanje minimalnega elementa.

Operacije na Fibonaccijevih kopicah

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:

 Fibonacci-Heap-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:

 Fibonacci-Heap-Union(H1,H2)
 H := Make-Fibonacci-Heap()
 min[H] := min[H1]  
 if (min[H1] = NIL) or (min[H2] ≠ NIL and min[H2] < min[H1])
 then min[H] := min[H2]
 n[H] := n[H1] + n[H2]  
 return H

Uporaba Fibonaccijevih kopic

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