# Operations On Binomial Heap – Union

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.**B**_{k }and B_{1 }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

**Case 1**

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**.

**Case 2**

If in union operation the heaps with **root b,c,d** are of same **order k** and **x point**s 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**.

**Case 3**

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]**.

**Case 4**

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**.

**Example**

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.

## Comments

So empty here ... leave a comment!