Min Heap Deletion Step By Step

How To Delete A Value In A Min Heap ?

Image for post
Image for post

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.
else
swap the replacement node with the smallest child node, and
repeat step 3.

Problem Example:

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.

Image for post
Image for post
Array that stores a Min binary heap

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.

Image for post
Image for post
The tree version of the binary heap array

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”.

Image for post
Image for post

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.

Image for post
Image for post

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”.

Image for post
Image for post

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”.

Image for post
Image for post

Now the heap property holds true and we are done ! You can find videos showing explaining this concept below:

Video Example of Binary Min Heap Deletion

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 !

Video Example of Binary Min Heap Deletion

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Recurrence Relation:

Image for post
Image for post

Resources:

(1) https://en.wikipedia.org/wiki/Binary_heap
(2)http://cs.carleton.edu/faculty/adalal/teaching/fall03/cs127/notes/oct22.pdf
(3) https://en.wikipedia.org/wiki/Heap_(data_structure)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store