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.