Fibonaccijeva kopica/Primer brisanja minimuma

Iz MaFiRaWiki

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:

 Fibonaccijeva-Kopica-Povezava(H,y,x)
 izmed korenov odstrani y,
 x postane starš od y
 stopnja[x] := stopnja[x] + 1
 mark[y] := false
 ZDRUŽITEV(H)
 for i :=0 to D(n[H])
   do A[i] := null
 for vsak koren w
   do x := w
      d := stopnja[x]
      while A[d] ≠ null
          do y := A[d]
             if ključ[x] > ključ[y]
               zamenjamo x z y 
             Fibonaccijeva-Kopica-Povezava(H, y, x)
             A[d] := null
            d := d+1
      A[d] := x
 min[H] := null
 for i := 0 to D(n[H])
   do if A[i] ≠ null
         then dodamo A[i] med korene
              if min[H] = null || ključ[A[i]] < ključ[min[H]]
                 then min[H] := A[i]
 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
Osebna orodja