Given a Binary Heap and an element present in the given Heap. The task is to delete an element from this Heap.

The standard deletion operation on Heap is to delete the element present at the root node of the Heap. That is if it is a Max Heap, the standard deletion operation will delete the maximum element and if it is a Min heap, it will delete the minimum element.

Process of Deletion:
Since deleting an element at any intermediary position in the heap can be costly, so we can simply replace the element to be deleted by the last element and delete the last element of the Heap.

• Replace the root or element to be deleted by the last element.
• Delete the last element from the Heap.
• Since, the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore, heapify the last node placed at the position of root.

Illustration 1:

Illustration 2:

Suppose the Heap is a Max-Heap as:
      10
    /   \ 
   5      3
  / \
 2   4

The element to be deleted is root, i.e. 10.

Process:
The last element is 4.

Step 1: Replace the last element with root, and delete it.
      4
    /   \ 
   5      3
  / 
 2   

Step 2: Heapify root.
Final Heap:
      5
    /   \ 
   4      3
  / 
 2   

C++ Program for Deletion in Heaps

#include<iostream>
using namespace std;
/*Heapify the heap using top down approach*/
void heapify(int a[],int n,int i)
{
	int parent = i;
        //checking whether the parent index is valid in the array or not
	if(i<n)
	{
		//formula for finding left subtree of parent
		int left = 2*i+1; 
		//formula for finding Right subtree of parent
		int right = 2*i+2; 
		//checking whether the children index is valid in the array or not
		if(left<n || right<n) 
		{
			//checking whether parent is less than children or not
			if(a[parent]<a[left] || a[parent]<a[right])
			{
                                //finding the largest children
				if(a[left]<a[right]) 
				{
                                        //swaping the parent with largest children
					swap(a[right],a[parent]); 
					heapify(a,n,right);  //Recursively heapify the heap
				}	
				else
				{
					swap(a[left],a[parent]);
					heapify(a,n,right);
				}
			}
		}
	}
}
// Function to delete the root from Heap
void DeleteElement(int a[],int &n)
{
	swap(a[0],a[n-1]); // swaping root and the last element
	n=n-1; // Decrease size of heap by 1
	heapify(a,n,0); //heapify the root node 
}
/*Printing the Heap*/
void printArray(int a[],int n)
{
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
}
/*Driver Function*/
int main()
{
	/*Initial Max Heap is */
	int a[] = {10,5,3,2,4};
	int n=5;
	cout<<"Before Deletion"<<endl;
	/*Printing the Array*/
	printArray(a,n);
	/*Deleting the root*/
	DeleteElement(a,n);
	cout<<"\nAfter Deletion"<<endl;
	/*Printing the Array*/
	printArray(a,n);
	return 0;
}

OUTPUT

Before Deletion
10 5 3 2 4
After Deletion
5 4 3 2