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
Slika 1.1 Zmanjšali bomo ključ 45 na 15.
Slika 1.2 Sedaj je v drevesu nov ključ.
Slika 1.3 Ker je 15 manjše od 24, se vozlišče odcepi. Ker starš ni koren, ga pobarvamo na črno.
Slika 1.4 Dobimo nov koren v drevesu.
Slika 1.5 Sedaj zmanjšamo ključ 35 na 5.
Slika 1.6 Ker je 5 manjše od 26 se odcepi in postane koren.
Slika 1.7 Ker je njegov starš označen, se prav tako odcepi in postane koren drevesa.
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)
