Wednesday, June 18, 2008

Binomial-Heap-Union

Binomial-Heap-Union (H1, H2)

The above Function unites two binomial heaps, H1 and H2. It uses an auxiliary operation ‘Binomial Heap-Merge’, and operation ‘Binomial-Link’ for processing.
Step 1 Creating an empty Heap
set H  Create-Binomial-Heap (x)
Step 2 Merging both the binomial heaps
set head [H]  Binomial-Heap-Merge (H1, H2)
Step 3 Is empty ?
if (head [H] = NLL) then
message : “Empty”
return (H)
Step 4 Initialization
set Prex  Nil
set x  head [H]
set nextx  sib [x]
Step 5 Loop, managing nodes at proper position.
while (nextx  Nil)
if ((deg [x]  deg [nextx]) or (sib [next x]  Nil and deg [sib [nextx]] = deg [x])
then
set Prex  x
set x  nextx
else if (key[x]  key [nextx]) then
call to Binomial-Link (nextx, x)
else if (Prex = Nil) then
set head [H]  nextx
else
set sib [Prex]  next x
call to Binomial Link (x, nextx)
set x  nextx
set nextx  sib [x]
Step 6 return value at the point of call
return (H)

No comments: