Fibonaccijeva kopica/Primer brisanja minimuma
Iz MaFiRaWiki
(Razlika med različicami)
| Različica od 18:46, 1 maj 2007 AleksandraVujasin (Pogovor | prispevki) ← Prejšnja različica |
Različica od 12:58, 17 maj 2007 AleksandraVujasin (Pogovor | prispevki) Naslednja različica → |
||
| Vrstica 27: | Vrstica 27: | ||
| '''Psevdo koda''': | '''Psevdo koda''': | ||
| - | Fibonacci-Heap-Extract-Min(H) | + | Fibonaccijeva-Kopica-Zbriši-Min(H) |
| z:= min[H] | z:= min[H] | ||
| - | if x ≠ NIL | + | if x ≠ null |
| otroke od z dodaj med korene od H | otroke od z dodaj med korene od H | ||
| - | p[x]:= NIL | + | p[x]:= null |
| odstrani z | odstrani z | ||
| if z = desni[z] | if z = desni[z] | ||
| - | then min[H]:=NIL | + | then min[H]:= null |
| else min[H]:=desni[z] | else min[H]:=desni[z] | ||
| - | CONSOLIDATE(H) | + | ZDRUŽITEV(H) |
| n[H] := n[H]-1 | n[H] := n[H]-1 | ||
| return z | return z | ||
Različica od 12:58, 17 maj 2007
Slika 1.1 Poiščemo min in ga odstranimo.
Slika 1.2 Poiščemo nov min in se postavimo na začetek. Otroci prejšnjega minimuma so sedaj koreni drevesa.
Slika 1.3 Pogledamo stopnjo prvega drevesa.
Slika 1.4 Pogledamo stopnjo drugega drevesa. Ker nista isti, gledamo naprej.
Slika 1.5 Pogledamo stopnjo naslednjega drevesa. Ker je različne stopnje od prvih dveh ne naredimo ničesar in gledamo naprej.
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.
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.
Slika 1.8 Novonastalo drevo je sedaj iste stopnje kot prvo, zato združimo še ti dve drevesi.
Slika 1.9 Naslednji koren je različne stopnje od predhodnih, zato ne naredimo ničesar.
Slika 1.10 Naslednje drevo je iste stopnje kot drugo, zato ju združimo.
Slika 1.11 Ostala so drevesa različne stopnje.
Slika 1.12 Postopek je končan.
Slika 1.13 Končna Fibonaccijeva kopica z novim minimalnim elementom.
Psevdo koda:
Fibonaccijeva-Kopica-Zbriši-Min(H) z:= min[H] if x ≠ null otroke od z dodaj med korene od H p[x]:= null odstrani z if z = desni[z] then min[H]:= null else min[H]:=desni[z] ZDRUŽITEV(H) n[H] := n[H]-1 return z
