Operations On Binomial Heap – Union

http://install4install.com

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 :

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.

Screen Shot 2014-06-05 at 4.01.45 PM

Fig 1 : Case 1

 

Case 2

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.

Screen Shot 2014-06-05 at 4.36.25 PM

Fig 2 : Case 2

 

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

Screen Shot 2014-06-10 at 12.43.29 PM

Fig 3 : Case 3

 

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.

Screen Shot 2014-06-10 at 12.54.47 PM

Fig 4 : Case 4

 

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.

Screen Shot 2014-06-10 at 4.47.05 PM

Fig 5 : Heaps h1 and h2

Screen Shot 2014-06-11 at 9.54.02 AM

Fig 6 : Union of h1 and h2

 

 

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.

Screen Shot 2014-06-10 at 5.18.04 PM

Fig 7 : Case 3 applied

 

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.

Screen Shot 2014-06-10 at 5.23.56 PM

Fig 8 : Case 2 applied

 

 

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.

Screen Shot 2014-06-10 at 5.31.57 PM

Fig 9 : Case 3 applied

 

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.

Screen Shot 2014-06-10 at 5.40.50 PM

Fig 10 : Case 3 applied

 

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.

Screen Shot 2014-06-10 at 6.15.30 PM

Fig 11 : Case 3 applied

 



Short URL: http://tinyit.cc/f799fd
Author: Cusp2207 on June 11, 2014
Category: Computer Science, Data Structures
Tags:

Leave a Reply

Last articles