Fibonaccijeva kopica/Primer brisanja minimuma

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 17:15, 29 april 2007
AleksandraVujasin (Pogovor | prispevki)

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

Naslednja različica →
Vrstica 1: Vrstica 1:
-[[image:DeleteMin1.jpg]]<br>+<center>[[image:DeleteMin1.jpg]]<br>
-Slika 1.1 Poiščemo min in ga odstranimo.<br>+<center>Slika 1.1 Poiščemo min in ga odstranimo.<br>
-[[image:DeleteMin2.jpg]]<br>+<center>[[image:DeleteMin2.jpg]]<br>
-Slika 1.2 Poiščemo nov min in se postavimo na začetek. Otroci prejšnjega minimuma so sedaj koreni drevesa.<br>+<center>Slika 1.2 Poiščemo nov min in se postavimo na začetek. Otroci prejšnjega minimuma so sedaj koreni drevesa.<br>
-[[image:DeleteMin3.jpg]]<br>+<center>[[image:DeleteMin3.jpg]]<br>
-Slika 1.3 Pogledamo stopnjo prvega drevesa.<br>+<center>Slika 1.3 Pogledamo stopnjo prvega drevesa.<br>
-[[image:DeleteMin4.jpg]]<br>+<center>[[image:DeleteMin4.jpg]]<br>
-Slika 1.4 Pogledamo stopnjo drugega drevesa. Ker nista isti, gledamo naprej.<br>+<center>Slika 1.4 Pogledamo stopnjo drugega drevesa. Ker nista isti, gledamo naprej.<br>
-[[image:DeleteMin5.jpg]]<br>+<center>[[image:DeleteMin5.jpg]]</center><br>
-Slika 1.5 Pogledamo stopnjo naslednjega drevesa. Ker je različne stopnje od prvih dveh ne naredimo ničesar in gledamo naprej.<br>+<center>Slika 1.5 Pogledamo stopnjo naslednjega drevesa. Ker je različne stopnje od prvih dveh ne naredimo ničesar in gledamo naprej.</center><br>
-[[image:DeleteMin6.jpg]]<br>+<center>[[image:DeleteMin6.jpg]]</center><br>
-Slika 1.6 Pogledamo stopnjo naslednjega drevesa. Našli smo drevo z isto stopnjo kot jo ima prejšnje drevo, zato drevesi združimo. Manjši postane koren (starš) večjemu.<br>+<center>Slika 1.6 Pogledamo stopnjo naslednjega drevesa. Našli smo drevo z isto stopnjo kot jo ima prejšnje drevo, zato drevesi združimo. Manjši postane koren (starš) večjemu.</center><br>
-[[image:DeleteMin7.jpg]]<br>+<center>[[image:DeleteMin7.jpg]]</center><br>
-Slika 1.7 Gledamo novo nastalo drevo in ugotovimo, da ima isto stopnjo kot prvo. Zato ju združimo. Večje drevo postane levi otrok manjšega drevesa.<br>+<center>Slika 1.7 Gledamo novo nastalo drevo in ugotovimo, da ima isto stopnjo kot prvo. Zato ju združimo. Večje drevo postane levi otrok manjšega drevesa.</center><br>
-[[image:DeleteMin8.jpg]]<br>+<center>[[image:DeleteMin8.jpg]]</center><br>
-Slika 1.8 Novonastalo drevo je sedaj iste stopnje kot prvo, zato združimo še ti dve drevesi.<br>+<center>Slika 1.8 Novonastalo drevo je sedaj iste stopnje kot prvo, zato združimo še ti dve drevesi.</center><br>
-[[image:DeleteMin9.jpg]]<br>+<center>[[image:DeleteMin9.jpg]]</center><br>
-Slika 1.9 Naslednji koren je različne stopnje od predhodnih, zato ne naredimo ničesar.<br>+<center>Slika 1.9 Naslednji koren je različne stopnje od predhodnih, zato ne naredimo ničesar.</center><br>
-[[image:DeleteMin10.jpg]]<br>+<center>[[image:DeleteMin10.jpg]]</center><br>
-Slika 1.10 Naslednje drevo je iste stopnje kot drugo, zato ju združimo.<br>+<center>Slika 1.10 Naslednje drevo je iste stopnje kot drugo, zato ju združimo.</center><br>
-[[image:DeleteMin11.jpg]]<br>+<center>[[image:DeleteMin11.jpg]]</center><br>
-Slika 1.11 Ostala so drevesa različne stopnje.<br>+<center>Slika 1.11 Ostala so drevesa različne stopnje.</center><br>
-[[image:DeleteMin12.jpg]]<br>+<center>[[image:DeleteMin12.jpg]]</center><br>
-Slika 1.12 Postopek je končan.<br>+<center>Slika 1.12 Postopek je končan.</center><br>
-[[image:DeleteMin13.jpg]]<br>+<center>[[image:DeleteMin13.jpg]]</center><br>
-Slika 1.13 Končna Fibonaccijeva kopica z novim minimalnim elementom.<br>+<center>Slika 1.13 Končna Fibonaccijeva kopica z novim minimalnim elementom.</center><br>
'''Psevdo koda''': '''Psevdo koda''':
Vrstica 30: Vrstica 30:
z:= min[H] z:= min[H]
if x ≠ NIL if x ≠ NIL
- then for each child x of z+ otroke od z dodaj med korene od H
- do add x to the root list of H+
p[x]:= NIL p[x]:= NIL
- remove z from the root list of H+ odstrani z
- if z = right[z]+ if z = desni[z]
then min[H]:=NIL then min[H]:=NIL
- else min[H]:=right[z]+ else min[H]:=desni[z]
CONSOLIDATE(H) CONSOLIDATE(H)
n[H] := n[H]-1 n[H] := n[H]-1
return z return z

Različica od 18:46, 1 maj 2007

image:DeleteMin1.jpg
<center>Slika 1.1 Poiščemo min in ga odstranimo.
<center>image:DeleteMin2.jpg
<center>Slika 1.2 Poiščemo nov min in se postavimo na začetek. Otroci prejšnjega minimuma so sedaj koreni drevesa.
<center>image:DeleteMin3.jpg
<center>Slika 1.3 Pogledamo stopnjo prvega drevesa.
<center>image:DeleteMin4.jpg
<center>Slika 1.4 Pogledamo stopnjo drugega drevesa. Ker nista isti, gledamo naprej.
<center>image:DeleteMin5.jpg

Slika 1.5 Pogledamo stopnjo naslednjega drevesa. Ker je različne stopnje od prvih dveh ne naredimo ničesar in gledamo naprej.

image:DeleteMin6.jpg

Slika 1.6 Pogledamo stopnjo naslednjega drevesa. Našli smo drevo z isto stopnjo kot jo ima prejšnje drevo, zato drevesi združimo. Manjši postane koren (starš) večjemu.

image:DeleteMin7.jpg

Slika 1.7 Gledamo novo nastalo drevo in ugotovimo, da ima isto stopnjo kot prvo. Zato ju združimo. Večje drevo postane levi otrok manjšega drevesa.

image:DeleteMin8.jpg

Slika 1.8 Novonastalo drevo je sedaj iste stopnje kot prvo, zato združimo še ti dve drevesi.

image:DeleteMin9.jpg

Slika 1.9 Naslednji koren je različne stopnje od predhodnih, zato ne naredimo ničesar.

image:DeleteMin10.jpg

Slika 1.10 Naslednje drevo je iste stopnje kot drugo, zato ju združimo.

image:DeleteMin11.jpg

Slika 1.11 Ostala so drevesa različne stopnje.

image:DeleteMin12.jpg

Slika 1.12 Postopek je končan.

image:DeleteMin13.jpg

Slika 1.13 Končna Fibonaccijeva kopica z novim minimalnim elementom.

Psevdo koda:

 Fibonacci-Heap-Extract-Min(H)
 z:= min[H]
 if x ≠  NIL
 otroke od z dodaj med korene od H
 p[x]:= NIL
 odstrani z 
 if z = desni[z]
 then min[H]:=NIL
 else min[H]:=desni[z]
 CONSOLIDATE(H)
 n[H] := n[H]-1
 return z
Osebna orodja