Heap : Removing the min element using BubbleDown

We are discussing min heap here. Extracting min from the heap is same as insertion in heap that we discussed earlier. In insertion, we used bubbling up (or sifting up) method, but in extract-min we will use bubbling down (or sifting down) method.

Pseudocode:

1. Copy the last value in the array to the root;
2. Remove last element, decrease heap's size by 1;(as we are using array)
3. Bubble down root's value if heap property between the nodes is violated. Bubbling down is done as following:
• if current node has no children, it is over;
• if current node has one child: check, if heap property is broken, then swap current node's value and child value; so we bubble down the child;
• if current node has two children: find the smaller of them. If heap property is broken, then swap current node's value and selected child value; bubble down the child.
4. Repeat step 3 until heap property is restored at that particular child.

Example
 Consider the following heap:

So applying first step, we remove 4, and copy last element i.e 13 to the first position.

wrong bubble down - Now we have to bubble down. So, lets bubble down 13 to 8, i.e. larger of 2 children:

Now, this is wrong, as (min) heap property at first node is still not satisfied as 8 is still larger than 4. So, better strategy is to swap the parent with smaller children

right method - swapping parent with smaller children

But still heap property is not satisfied, and as 13 with 4.

Finally we have following heap :

Here is the code in java:

public int extractMin() throws Exception {
 if (isEmpty())
  throw new UnderFlowException("Heap is empty");
 swap(0,currentSize-1);
 currentSize--;
 if (currentSize != 0)
  bubbleDownIterative(0);
 return Heap[currentSize];
}

Thanks