The union of two heaps is the merging root lists by root degree.But if we simply merge two heaps then a problem can arise.There may be a chance that we get two or more trees of same root degree.This violates the property of binomial heap.To deal with this problem we have four cases and solution to these cases respectively. Referring to all figures we choose arbitrary names like :
- x is the second node of merged heaps.
- prev-x points to previous node of x.
- next-x points to next node of x.
- sibling[next-x] points to next node of next-x.
- Bk and B1 are Binomial Heaps of order k and 1 respectively.
- We apply different cases according to the situation until next-x becomes nil.
Cases in union of binomial heaps
If we merge heaps and have a case like x points to binomial heap of order k and next-x points to binomial heap of order 1 then ,then we need to shift our pointers towards right.x will now point to binomial heap with order 1.next-k will point to heap with root node d and prev-x will point to heap with root node b and order k.
If in union operation the heaps with root b,c,d are of same order k and x points to heap of order k and root node b,next-x points to next heap of x with same order and root node c and sibling[next-x] points to next heap of next-x again with same order and root node d then pointers shift by one. x now points to heap with root node c,next-x points heap with root d and prev-x points to heap with root b.
After the union operation,if b,c are of same order and key[x] is less than key[next[x]] then c becomes the left child of b and x remain on pointing to b but next-z now points to points to d which was earlier pointed by sibling[next-x].
The pointer points to same binomial heaps as in case 3 except the difference that key of x is greater than key[next[x]].In this case,b becomes the child of c.c is pointed by x and d is pointed by next-x.
Consider two heaps h1 and h2 as given in Fig 5.The union operation has to be performed on these two heaps.h1 has binomial trees of order 0,1 and 2.h2 has binomial trees of order 0,1 and 3.At the point of union operation both the heaps are combined together but the resultant structure does not follows heap property i.e the resultant structure has binomial trees of same order.In Fig 5,two trees with root 2 and 5 are of order 0 and two trees with roots 1 and 3 are of order 1 violating the property of heaps.In order to make a structure satisfying heap properties we follow case according to the situation.The union of h1 and h2 is shown in Fig 6.
In Fig 7,2 is less than 5 and both the trees are of same order i.e 0 so case 3 is followed in which root pointed by next-x(5) becomes the child of x(2) and pointer next-x shifts to right i.e it shifts to 1 and sibling[next-x] also shifts pointer to right i.e to 3.
In Fig 8,all three binomial trees pointed by x,next-x and sibling[next-x] are of same order i.e 1 so case 2 is followed in which all three pointers shift to right by one i.e x will point to 1,next-x will point to 3 and sibling[next-x] will point to 7.
In Fig 9,Case 3 is followed as root 1 is less than root 3 and their trees are of same order.Tree with root 3 becomes child of tree with root 1.
In Fig 10,Case 3 is followed again as root 1 is less than root 7 and their trees are of same order i.e. 2.Tree with root 1 becomes the child of tree with root 7.
In Fig 11,Case 3 is followed as 1 is less than 4 and their trees are of same order i.e.3.Tree with root 1 becomes the child of tree with root 4. The next-x becomes nil and so the process of applying cases stop here.We get two binomial trees of different orders.They are of order 1 and 4 respectively.Union of heaps is done satisfying all the properties of binomial heap.