Operations on Binomial Heap – Extract-min

http://install4install.com

In Extract-Min operation node with minimum key is deleted from the binomial heap h.The running time to extract minimum value is  O(log n).The steps followed  are :

Given the binomial heap h in Fig 1.The first step is to find the root with minimum key.Node with value 1 is smallest so it is deleted and h is broken down into h and h’(Fig 2).

Screen Shot 2014-06-11 at 2.13.48 PM

Fig 1 : Binomial heap h

Fig 2 : Binomial heaps h and h'

Fig 2 : Binomial heaps h and h’

 

Perform the union operation on h and h’.

Screen Shot 2014-06-11 at 2.32.37 PM

Fig 3 : Union on h and h’

 

After the union operation on h and h’ the structure seems like as given in Fig 4

Screen Shot 2014-06-11 at 2.37.11 PM

Fig 4 : Structure after union of h and h’

 

Different cases are performed according to the situation.x points to 11,next-x points to 2,sibling[next-x] points to 3 as shown in Fig 5

Screen Shot 2014-06-11 at 2.38.52 PM

Fig 5 : Structure after union of h and h’

 

Case 1 is applied in Fig 6.x now points to 2,next-x points to 3 and sibling[next-x] points to 7.

Screen Shot 2014-06-11 at 2.43.45 PM

Fig 6 : Case 1 applied

 

Case 3 is applied to Fig 7.Trees with root 2 and 3 are of same order i.e. 1 and 2 is less than 3 so 3 becomes the child of 2.next-x will now point to 7 and sibling[next-x] will point to 4.

Screen Shot 2014-06-11 at 2.48.00 PM

Fig 7 : Case 3 applied

 

 

Case 3 is applied again in Fig 8.2 is less than 7 so 7 becomes the child of 2.next-x will now point to 4.

Screen Shot 2014-06-11 at 3.31.52 PM

Fig 8 : Case 3

 

Case 3 is applied in Fig 9 as 2<4 .So 4 becomes the child of 2.x now points to 2 and next-x points to null.Thus the process stops here.

Screen Shot 2014-06-11 at 3.41.23 PM

Fig 9 : Case 3 applied



Short URL: http://tinyit.cc/29008e
Author: Cusp2207 on June 11, 2014
Category: Computer Science, Data Structures
Tags:
2 responses to “Operations on Binomial Heap – Extract-min”
  1. Catterpiller says:

    Thanks. I want to learn more, can you point me to the right source?

Leave a Reply for Cusp2207

Last articles