Deleting the element from the heap

Here we will discuss deletion of element from min heap.

Pseudocode for deletion from heap

1. Find the index of the element to be deleted from the heap. This takes O(n) time.(If you already have the index, please skip this step)
2. Remove the element from the heap
3. Move the root element to the element to be deleted location
4. Move the last element to the first position
5. Decrease array size by 1
6. Now bubble down on the array(like we did in extract min). Bubbling down (or sifting down) is done as follows : 
• 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.
7. Repeat step 6, until the heap property is satisfied.

Example

Consider the following heap:

Suppose we want to delete element 9. So, we first nullify it and move to 4 to 9th location:

Now, as the root position is empty, we move last element i.e. 13 to root.

Now the process of bubbling down starts. We see that at the root node, 12 is greater than 4 and 8. So we swap it with smaller of children i.e. 4.

But again the heap property is not restored, as 13 is still larger than 4 and 4. So bubbling down again:

But still 13 is greater than 11, and hence heap property is still not satisfied:

Finally, min heap property is satisfied, and we are done.

Thanks.