Fibonaccijeva kopica/Primer manjšanja ključa

Iz MaFiRaWiki

< Fibonaccijeva kopica(Razlika med različicami)

Različica od 13:57, 28 april 2007

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:

 Fibonacci-Heap-Decrease-Key(H,x,k)
 if k > key[x]
 then error "new key is greater than current key"
 key[x] := k
 y := p[x]
 if y <> NIL and key[x] then CUT(H, x, y)
 CASCADING-CUT(H,y)
 if key[x] then min[H] := x 
 CUT(H,x,y)
 Remove x from the child list of y, decrementing degree[y]
 Add x to the root list of H 
 p[x]:= NIL
 mark[x]:= FALSE 
 CASCADING-CUT(H,y)
 z:= p[y]
 if z <> NIL 
 then if mark[y] = FALSE
 then mark[y]:= TRUE
 else CUT(H, y, z)
 CASCADING-CUT(H, z)
Osebna orodja