How To Delete A Value In A Min Heap ?
In this article I will show you how to delete an element from a Min Heap also known as a Minimum Heap. You will learn what a heap data structure is, and the algorithm to delete an element from a Min Heap. In this article you will also find helpful videos that show and easily explains how to delete an element from a Min Heap. Let’s get started !
A heap data structure in computer science is a special tree that satisfies the heap property, this just means that the parent is less than or equal to the child node for a minimum heap A.K.A min heap, and the parent is greater than or equal to the child node for a maximum heap A.K.A max heap. In this article I will talk specifically about binary heaps, so each node in our tree will have at most two children. Yes there are more than just binary heaps. The binary heap was created by J.W. J. Williams in 1964 for heapsort.
A binary heap is a binary tree with two other constraints
1) Shape Property: A binary heap is a complete binary tree, this means all of the levels of the tree are completely filled except possibly the last level. The nodes are filled from left to right.
2) Heap Property: The value stored in each node is either (greater than or equal to) OR (less than or equal to ) it’s children depending if it is a max heap or a min heap.
Min Heap Deletion Algorithm:
1. Delete the node that contains the value you want deleted in the heap. 2. Replace the deleted node with the farthest right node. 3. Heapify (Fix the heap):
if the heap property holds true
then you are done.
else if the replacement node value <= its parent nodes value
then swap them, and repeat step 3.
swap the replacement node with the smallest child node, and
repeat step 3.
The array below stores a Minimum (Min) binary heap. Draw the tree version of the binary heap, then remove the minimum value/element and show the heap in its tree form.
Step 0: Change the Array Data Structure into a Tree
In order to change an array structure into the tree version of the binary heap, we start from the left to the right of the array, and then insert values into the binary heap from top to bottom and left to right.
Step 1: Delete the node that contains the value you want deleted in the heap.
The value that we want to delete is the minimum value or element in the array which is at the root of the tree. This is the node that contains the value “2”.
Step 2: Replace the deleted node with the farthest right node.
The farthest right node is the node that contains the value “9”. So we will replace the deleted node with this node.
Step 3: Heapify (Fix the heap):
The value “9” at the root of the tree is greater than both of its children, the nodes containing the value “5” and “7”. We need to swap the “9” with the smallest child, the node containing the value “5”.
Since the heap property that states that the parent node must contain a value smaller than it’s children has not been satisfied for the replacement node containing the value “9”, we must swap the replacement node with the node of its children that contain the smaller value. So we swap the node containing the value “9” and “8”.
Now the heap property holds true and we are done ! You can find videos showing explaining this concept below:
If you would like to learn more about Computer Science and Algorithm Analysis , you can take my online course here. I also have a course on Udemy.com called Recurrence Relation Made Easy where I help students to understand how to solve recurrence relations and asymptotic terms such as Big-O, Big Omega, and Theta. You can check out my YouTube channel of videos where I solve recurrence relations and perform algorithm analysis on code that anyone can check out for free !
Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:
Video Tutorials on Recurrence Relation:
Video Tutorial on Algorithm Analysis: