How to delete an element from the max heap

A heap is a binary tree that meets the heap property. Heap can be of two types:

Min heap: The element of each node is larger than or equal to the element at its parent. The node with the lowest value is the root.

Max heap: The element of each node is smaller than the element at its parent. The highest value element is at the root.

Building a heap from an array ensures that the heap order property is maintained after every input. The input is checked if it is smaller than its parent. If it's not, it is swapped.

Delete operation

When it comes to deleting an element from the max heap, there are two cases:

Case-01: Deletion of the leaf nodes

This case is straightforward to handle. We delete/disconnect the leaf node from the max heap in this case. After deleting the leaf node, we don’t need to change any value in the max heap.

Case-02: Deletion of some other node

This case is strenuous as deleting a node other than the leaf node disturbs the heap properties. This case takes two steps for deletion:

Delete the selected element from the given heap tree and replace the value of the last node with deleted node.
Check the max heap properties for the entire heap and keep calling the heapify() function until we get the max heap.

Let's visualize it from an example. In this example, we delete the root node:


void deleteNode(int array[], int node) //function for deleting node
{
  int i=0;
  for (i = 0; i < size; i++)
  {
    if (node == array[i]) //finding selected node
      break;
  }
  swap(&array[i], &array[size - 1]); //swapping with last node
  size -= 1; //decrementing size after deleting node 
  
  for (int i = size / 2 - 1; i >= 0; i--)
  {
    heapify(array, i); //heapifying 
  }
}
// Driver Code 
int main() 
{ 
	
	int array[] = {1, 5, 6, 8, 9, 7, 3};
	size = sizeof(array) / sizeof(array[0]); //size
	build_heap(array); //creating heap
  	cout << "Heapify Array: ";
    printArray(array); //print node
    deleteNode(array,9); //deleting root node
  	
    cout << "After Deleting root \nHeapify Array:  ";
	printArray(array);    //printing node
		
	return 0; 
}

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

How to delete an element from the max heap

Delete operation

Implementation

Explanation