Wednesday, June 18, 2008

Fibonacci Heap Consolidate

Consolidate (H)

The above Procedure consolidates the rooted trees in the root list of Fibonacci Heap H until all the trees have distinct degrees. It also uses an auxilliary ‘A’, if A [i] = y, then y is currently a root with deg [y] i.
Step 1 Loop, Initialization
for i  0 to D(n [H])
set A [i]  Nil.
Step 2 loop 1, processing of each node in the root list
for each node w in the root list of H
set x  w
set d  deg [x]
loop 2
while ( A [d]  Nil)
set y  A[d]
if (key [x] > key [y]) then
set x  y
call to Fibonacci-Link (H, y,x).
set A [d]  Nil.
set d  d + 1.
end loop 2
end loop 1
set A [d]  x
Step 3 Initialization, empties the root list.
set min [H]  Nil
Step 4 loop, reconstruction
for i  0 to D(n [H])
if ( A [i]  Nil) then
add A [i] to the root list of H.
if (min [H] = Nil or key [A [i] < key (min [H])
set min [H]  A [i]
end loop

No comments: