Wednesday, June 18, 2008


Binomial-Heap-Extract-Min (H)

The above function extracts a node with minimum key from the Heap. It uses ‘Binomial-Heap-Union’ operation.
Step 1 Finding ‘x’
First find the node ‘x’ having minimum key in the root list of H, and remove the node from the list.
Step 2 Creating an empty binomial heap.
H1  Create-Binomial-Heap (x)
Step 3 Adjusting pointers
reverse the linked list order of x's children, and set head [H1] as new head pointer.
Step 4 Uniting H and H1 binomial heaps.
H  Binomial-Heap-Union (H, H1)
Step 5 Return value at the point of call
return (x)

No comments: