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

Perform the union operation on h and h'.

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

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

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

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.

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.

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.