Uniting two binomial heaps
The operation of uniting two binomial heaps is used as a subroutine by most of the remaining operations. The BINOMIAL-HEAP-UNION procedure repeatedly links binomial trees whose roots have the same degree. The following procedure links the Bk-1 tree rooted at node y to the Bk-1 tree rooted at node z; that is, it makes z the parent of y. Node z thus becomes the root of a Bk tree.
BINOMIAL-LINK(y, z)
1 p[y] ← z
2 sibling[y] ← child[z]
3 child[z] ← y
4 degree[z] ← degree[z] + 1
The BINOMIAL-LINK procedure makes node y the new head of the linked list of node z's children in O(1) time. It works because the left-child, right-sibling representation of each
binomial tree matches the ordering property of the tree: in a Bk tree, the leftmost child of the root is the root of a Bk-1 tree.
The following procedure unites binomial heaps H1 and H2, returning the resulting heap. It destroys the representations of H1 and H2 in the process. Besides BINOMIAL-LINK, the
procedure uses an auxiliary procedure BINOMIAL-HEAP-MERGE that merges the root lists of H1 and H2 into a single linked list that is sorted by degree into monotonically increasing order. The pseudo-code for merge is here:-
Binomial-Heap-Merge(H1;H2)
1 H Ã Make-Binomial-Heap()
2 if key[head[H2]] < key[head[H1]]
3 then head[H] Ã head[H2]
4 current2 Ã sibling[head[H2]]
5 current1 Ã head[H1]
6 else head[H] Ã head[H1]
7 current1 Ã sibling[head[H1]]
8 current2 Ã head[H2]
9 current à head[H]
10 while current1 6= NIL and current2 6= NIL
11 do if key[current1] > key[current2]
12 then sibling[current] Ã current2
13 current à sibling[current]
14 current2 Ã sibling[current2]
15 else
16 sibling[current] Ã current1
17 current à sibling[current]
18 current1 Ã sibling[current1]
19 if current1 = NIL
20 then tail à current2
21 else tail à current1
22 while tail 6= NIL
23 do sibling[current] Ã tail
24 current à sibling[current]
25 tail à sibling[tail]
26 return head[H]
This routine starts by creating and initialising a new heap, on lines 1 through
9. The code maintains three pointers. The pointer current, stores the root of
the tree most recently added to the heap. For the two input heaps, current1
and current2 record their next unprocessed root nodes. In the while loop, these
pointers are used to add trees to the new heap, while maintaining the desired
monotonic ordering within the resulting list. Finally, the case where the two
heaps have differing numbers of trees must be handled - this is done on lines 19
through 25. continue:-uniting4.php
