Fibonaccijeva kopica/Primer manjšanja ključa

Iz MaFiRaWiki

< Fibonaccijeva kopica(Razlika med različicami)
Različica od 18:50, 1 maj 2007
AleksandraVujasin (Pogovor | prispevki)

← Prejšnja različica
Trenutna različica
AleksandraVujasin (Pogovor | prispevki)

Vrstica 17: Vrstica 17:
'''Psevdo koda''': '''Psevdo koda''':
- Fibonacci-Heap-Decrease-Key(H,x,k)+ 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] if k > ključ[x]
- napaka "novi ključ je večji od sedanjega" + napaka "novi ključ je večji od prvotnega"
ključ[x] := k ključ[x] := k
y := p[x] y := p[x]
- if y ≠ NIL and key[x] then CUT(H, x, y)+ if y ≠ null && ključ[x]
- CASCADING-CUT(H,y)+ then CUT(H, x, y)
- if ključ[x] then min[H] := x + CASCADING-CUT(H,y)
- CUT(H,x,y)+ if ključ[x] < ključ[min[H]]
- p[x]:= NIL+ then min[H] := x
- 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)+

Trenutna različica

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