Wednesday, June 18, 2008


Fibonacci-Heap-Extract-Min (H)

The above Function extracts the node having minimum key from the fibonacci heap H. For convenience we assume that, when a node is removed from a root list, pointers remaining in the list are updated, but pointer in the extracted nodes remain unaltered.
Step 1 Initialization
set z  min [H]
Step 2 If not empty
if (z  Nil ) then
for each child x of z
add x to the root list of H
set Parent [x]  Nil
Step 3 Remove z from the root list of H
if (z = right [z] ) then
set min [H ]  Nil
set min [H]  right [z]
call to consolidate (H)
Step 4 Increase the number of nodes.
set n [H]  n [H] + 1.
Step 5 Return value at the point of call
return (z).

No comments: