Fibonaccijeva kopica/Primer brisanja minimuma

Iz MaFiRaWiki

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

← Prejšnja različica
Različica od 17:15, 29 april 2007
AleksandraVujasin (Pogovor | prispevki)

Naslednja različica →
Vrstica 29: Vrstica 29:
Fibonacci-Heap-Extract-Min(H) Fibonacci-Heap-Extract-Min(H)
z:= min[H] z:= min[H]
- if x <> NIL+ if x NIL
then for each child x of z then for each child x of z
do add x to the root list of H do add x to the root list of H

Različica od 17:15, 29 april 2007

image:DeleteMin1.jpg
Slika 1.1 Poiščemo min in ga odstranimo.
image:DeleteMin2.jpg
Slika 1.2 Poiščemo nov min in se postavimo na začetek. Otroci prejšnjega minimuma so sedaj koreni drevesa.
image:DeleteMin3.jpg
Slika 1.3 Pogledamo stopnjo prvega drevesa.
image:DeleteMin4.jpg
Slika 1.4 Pogledamo stopnjo drugega drevesa. Ker nista isti, gledamo naprej.
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
 then for each child x of z
 do add x to the root list of H
 p[x]:= NIL
 remove z from the root list of H
 if z = right[z]
 then min[H]:=NIL
 else min[H]:=right[z]
 CONSOLIDATE(H)
 n[H] := n[H]-1
 return z
Osebna orodja