Fibonaccijeva kopica/Primer manjšanja ključa

Iz MaFiRaWiki

image:DecreaseKey1.jpg

Slika 1.1 Zmanjšali bomo ključ 45 na 15.

image:DecreaseKey2.jpg

Slika 1.2 Sedaj je v drevesu nov ključ.

image:DecreaseKey3.jpg

Slika 1.3 Ker je 15 manjše od 24, se vozlišče odcepi. Ker starš ni koren, ga pobarvamo na črno.

image:DecreaseKey4.jpg

Slika 1.4 Dobimo nov koren v drevesu.

image:DecreaseKey5.jpg

Slika 1.5 Sedaj zmanjšamo ključ 35 na 5.

image:DecreaseKey6.jpg

Slika 1.6 Ker je 5 manjše od 26 se odcepi in postane koren.

image:DecreaseKey7.jpg

Slika 1.7 Ker je njegov starš označen, se prav tako odcepi in postane koren drevesa.

image:DecreaseKey8.jpg

Slika 1.8 Ker je tudi njegov starš označen, se prav tako odcepi in postane koren drevesa. Ker smo prišli do korena, je postopka konec.

Psevdo koda:

 CUT(H,x,y)
 odstrani x (otrok od y-a), zniža stopnjo y-a
 x postane koren
 p[x] := null
 mark[x] := false
 CASCADING-CUT(H,y)
 z := p[y]
 if z ≠ null 
   then if mark[y] = false
        then mark[y] := true
        else CUT(H, y, z)
             CASCADING-CUT(H, z)
 Fibonaccijeva-Kopica-Zmanjšaj-Ključ(H,x,k)
 if k > ključ[x]
 napaka "novi ključ je večji od prvotnega"  
 ključ[x] := k
 y := p[x]
 if y ≠ null && ključ[x] 
   then CUT(H, x, y)
        CASCADING-CUT(H,y)
 if ključ[x] < ključ[min[H]]
 then min[H] := x
Osebna orodja