Facebook

Operations on Binomial Heap – Extract-min

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 :

  • Find the root (say x) with minimum key.
  • Delete the root.
  • Break the binomial heap into h and h'.
  • Perform the union operation to h and h'.

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

Fig 1 :Binomial heap h
Fig 2 : Binomial heaps h and h'

 

Perform the union operation on h and h'.

Fig 3

 

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

Fig 4 : 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

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.

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.

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.

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.

5 (100%) 1 vote

Comments

This post currently has 2 responses

Leave a Reply to Cusp2207 Cancel reply

Your email address will not be published. Required fields are marked *

Sidebar