Wednesday, June 18, 2008

Fibonacci-Heap-Union

Fibonacci-Heap-Union (H1, H2)

The above Function unites two fibonacci heaps H1 and H2 by simply concatenating their root lists. The new min [H] pointer points to the minimum key node of the resulting fibonacci heap H.
Step 1 Creating an empty fibonacci heap
set H  create-Fibonacci-Heap
Step 2 Initialization
set min [H]  min [H1]
Step 3 Concatenating the root list of H2 with root list of H
if (min [H1] = Nil or (min [H2]  Nil and min [H2] < min [H1])) then
set min [H]  min [H2]
Step 4 Addition of new nodes
set n [H]  n[H1] + n [H2]
Step 5 Free the objects H1 and H2, return value at the points of call
return (H)

No comments: