### C++ Deletion in Heaps

Deletion in Heaps

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   4The 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 Heapvoid 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 Deletion10 5 3 2 4After Deletion5 4 3 2`

#### More Articles of Shaik Ismail:

Name Views Likes
C++ Counting Sort 2027 1
C++ Shutdown Using C++ Code 5745 1
C++ Basics of Graph Data Structure 1648 0
C++ Selection Sort 1438 0
C++ Mirror Binary Tree 836 0
C++ AVL Rotations 2495 0
C++ Merge Sort 6012 0
C++ Graph Representation 703 0
C++ Insertion Sort 627 0
C++ Heap Sort 1582 0
C++ BFS in Graph 4547 0
C++ Deletion in Heaps 6538 0
C++ Check if a binary tree is a BST or not 1576 0
C++ Deletion of Nodes in BST 5297 0
C++ Identical Binary Trees 557 0
C++ Insertion of Nodes in BST 550 0
C++ Single Number LeetCode Bit Manipulation 1982 0
C++ Lowest Common Ancestor 1516 0
C++ Kth Largest Element in BST 858 0
C++ Height of the Binary Tree (Code) 976 0
C++ DFS for a Graph 6023 0
C++ Diameter of a Binary Tree 1914 0
C++ Binary Tree Representation and Traversals (Code) 664 1
C++ Basics of Tree Data Structure PART - 2 700 0
C++ Vertical Order Traversal of a Binary Tree 887 0
Basics of Tree Data Structure PART - 1 426 0
C++ Basics of Heap Data Structure 1420 0
CPP Project or program to get six subjects marks of a student and then calculate its total, average and percentage and display them on the screen 419 0
C++ Basics of BST Part - 1 750 0
C++ Searching in BST 629 0
C++ AVL Tree 883 0
Tree 446 1
C++ Missing Number(LeetCode) 2201 0
C++ Insertion of Elements in Heap 3906 0
C++ Level Order Traversal of a Binary Tree 956 0
C++ Binary Tree 722 0
C++ DNF Algorithm for Sorting 0,1,2 1780 0
C++ Wave Sort 944 0
C++ Binary Tree is a SumTree or Not 411 0
C++ Deletion in AVL Trees 686 0
C++ Quick Sort 4763 0
C++ Power of Two Leetcode BitManipulation 1000 0
C++ Bottom View of a Binary Tree 437 0
C++ Kth Smallest Element in BST 960 0
C++ Bubble Sort 713 0
C++ Top View of a Binary Tree 488 0
C++ Majority Element (LeetCode) 1043 0
C++ Sum of all leaf nodes 414 0
C++ Graph Representation (Adjacency list) 2736 0
C++ Count set bits in an integer 1510 0