Fibonaccijeva kopica/Primer vstavljanja drevesa

Iz MaFiRaWiki

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

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

Naslednja različica →
Vrstica 1: Vrstica 1:
-[[image:Insert1.jpg]]<br>+<center>[[image:Insert1.jpg]]</center><br>
-Slika 1.1 Ustvarimo novo drevo z enim elementom (v našem primeru s ključem 21).<br>+<center>Slika 1.1 Ustvarimo novo drevo z enim elementom (v našem primeru s ključem 21).</center><br>
-[[image:Insert2.jpg]]<br>+<center>[[image:Insert2.jpg]]</center><br>
-Slika 1.2 Novo drevo damo na levo stran od minimuma, kjer postane koren kopice. Preverimo minimum.<br>+<center>Slika 1.2 Novo drevo damo na levo stran od minimuma, kjer postane koren kopice. Preverimo minimum.</center><br>
-<br>+
'''Psevdo koda''': '''Psevdo koda''':
Fibonacci-Heap-Insert(H,x) Fibonacci-Heap-Insert(H,x)
- degree[x] := 0 + stopnja[x] := 0
p[x] := NIL p[x] := NIL
- child[x] := NIL + otrok[x] := NIL
- left[x] := x + levi[x] := x
- right[x] := x + desni[x] := x
- mark[x] := FALSE + mark[x] := FALSE
- concatenate the root list containing x with root list H +
if min[H] = NIL or key[x] then min[H] := x if min[H] = NIL or key[x] then min[H] := x
n[H]:= n[H]+1 n[H]:= n[H]+1

Različica od 18:41, 1 maj 2007

image:Insert1.jpg

Slika 1.1 Ustvarimo novo drevo z enim elementom (v našem primeru s ključem 21).

image:Insert2.jpg

Slika 1.2 Novo drevo damo na levo stran od minimuma, kjer postane koren kopice. Preverimo minimum.

Psevdo koda:

  Fibonacci-Heap-Insert(H,x)
  stopnja[x] := 0 
  p[x] := NIL 
  otrok[x] := NIL 
  levi[x] := x 
  desni[x] := x 
  mark[x] := FALSE    
  if min[H] = NIL or key[x] then min[H] := x 
  n[H]:= n[H]+1
Osebna orodja