Visually Explained Algorithms

I’ll begin by stating that inserting a node into the min-heap has been outlined in my other articles: Constructing Min-Heap from a Tree and Constructing Min-Heap from an Array.

As a quick recap, you add it as the last element in the tree. You compare it with its parent, and if its larger, you swap the parent and the child. You keep comparing it with each parent going up the tree until you reach a point where either the parent is smaller than the node you’re inserting, or the node has reached the root.

We’ll start by deleting the root node. The reason we’re deleting the root node is due to the underlying concept of the heap: the priority queue. The element with the highest priority is removed from the priority queue.

When deleting the root node, the last node becomes the new root node.

The root element might not be in the correct spot on the min-heap. Since 48 is larger than its children, it needs to trickle down into the correct position. We’ll follow the same approach as we did in the Constructing Min-Heap from a Tree article.

A comparison is made of the two children, 4 and 7, and the smallest value is chosen. Since 4 is smaller than 48, they swap positions.

Next, 5 and 8 are compared to obtain the smallest child of 48 again. Considering 5 is the smallest child, 48 is compared to 5. Node 5 is smaller than 48, so the two nodes are swapped.

Finally, 11 and 6 are compared. Node 6 is the smallest child, so it’s compared to 48. Node 48 is larger; therefore, the two nodes are swapped. Node 48 has no further comparisons to make. Min-Heap is achieved again after the deletion of the root node.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.


Leave a Reply