# 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%) 2 votes

## Comments

### This post currently has 2 responses

• Catterpiller says:

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

Sidebar