Fibonaccijeva kopica/Primer manjšanja ključa

Iz MaFiRaWiki

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

← Prejšnja različica
Različica od 18:50, 1 maj 2007
AleksandraVujasin (Pogovor | prispevki)

Naslednja različica →
Vrstica 1: Vrstica 1:
-[[image:DecreaseKey1.jpg]]<br>+<center>[[image:DecreaseKey1.jpg]]</center><br>
-Slika 1.1 Zmanjšali bomo ključ 45 na 15.<br>+<center>Slika 1.1 Zmanjšali bomo ključ 45 na 15.</center><br>
-[[image:DecreaseKey2.jpg]]<br>+<center>[[image:DecreaseKey2.jpg]]</center><br>
-Slika 1.2 Sedaj je v drevesu nov ključ.<br>+<center>Slika 1.2 Sedaj je v drevesu nov ključ.</center><br>
-[[image:DecreaseKey3.jpg]]<br>+<center>[[image:DecreaseKey3.jpg]]</center><br>
-Slika 1.3 Ker je 15 manjše od 24, se vozlišče odcepi. Ker starš ni koren, ga pobarvamo na črno.<br>+<center>Slika 1.3 Ker je 15 manjše od 24, se vozlišče odcepi. Ker starš ni koren, ga pobarvamo na črno.</center><br>
-[[image:DecreaseKey4.jpg]]<br>+<center>[[image:DecreaseKey4.jpg]]</center><br>
-Slika 1.4 Dobimo nov koren v drevesu.<br>+<center>Slika 1.4 Dobimo nov koren v drevesu.</center><br>
-[[image:DecreaseKey5.jpg]]<br>+<center>[[image:DecreaseKey5.jpg]]</center><br>
-Slika 1.5 Sedaj zmanjšamo ključ 35 na 5.<br>+<center>Slika 1.5 Sedaj zmanjšamo ključ 35 na 5.</center><br>
-[[image:DecreaseKey6.jpg]]<br>+<center>[[image:DecreaseKey6.jpg]]</center><br>
-Slika 1.6 Ker je 5 manjše od 26 se odcepi in postane koren.<br>+<center>Slika 1.6 Ker je 5 manjše od 26 se odcepi in postane koren.</center><br>
-[[image:DecreaseKey7.jpg]]<br>+<center>[[image:DecreaseKey7.jpg]]</center><br>
-Slika 1.7 Ker je njegov starš označen, se prav tako odcepi in postane koren drevesa.<br>+<center>Slika 1.7 Ker je njegov starš označen, se prav tako odcepi in postane koren drevesa.</center><br>
-[[image:DecreaseKey8.jpg]]<br>+<center>[[image:DecreaseKey8.jpg]]</center><br>
-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.<br>+<center>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.</center><br>
'''Psevdo koda''': '''Psevdo koda''':
Fibonacci-Heap-Decrease-Key(H,x,k) Fibonacci-Heap-Decrease-Key(H,x,k)
- if k > key[x]+ if k > ključ[x]
- then error "new key is greater than current key"+ napaka "novi ključ je večji od sedanjega"
- key[x] := k+ ključ[x] := k
y := p[x] y := p[x]
- if y <> NIL and key[x] then CUT(H, x, y)+ if y NIL and key[x] then CUT(H, x, y)
CASCADING-CUT(H,y) CASCADING-CUT(H,y)
- if key[x] then min[H] := x + if ključ[x] then min[H] := x
CUT(H,x,y) 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 p[x]:= NIL
mark[x]:= FALSE mark[x]:= FALSE
CASCADING-CUT(H,y) CASCADING-CUT(H,y)
z:= p[y] z:= p[y]
- if z <> NIL + if z NIL
then if mark[y] = FALSE then if mark[y] = FALSE
then mark[y]:= TRUE then mark[y]:= TRUE
else CUT(H, y, z) else CUT(H, y, z)
CASCADING-CUT(H, z) CASCADING-CUT(H, z)

Različica od 18:50, 1 maj 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 > ključ[x]
 napaka "novi ključ je večji od sedanjega"  
 ključ[x] := k
 y := p[x]
 if y ≠ NIL and key[x] then CUT(H, x, y)
 CASCADING-CUT(H,y)
 if ključ[x] then min[H] := x 
 CUT(H,x,y)
 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