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

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

Hi! You can learn more about extract-min operation in the following link : https://mitpress.mit.edu/sites/default/files/Chapter%2019.pdf