Introduction
Main Focus
Hey all, welcome back to Think Like A Programmer - where we cover programming concepts in bite-sized chunks.
For those of you that celebrate the Lunar new year, I hope that you guys are having a fantastic time with your loved ones and family. :)
Moving on to today’s article, we’ll finish up our three part series on heaps - which are used to find the maximum or minimum elements of a list of elements in the fastest time.
This is a continuation of last week’s article where we looked at
How to represent a heap in memory
How to construct a heap from a list of elements from scratch?
So, what’s left for us to go through with heaps - The short answer is just the time complexity of the max-heapify operations that we mentioned the week before.
This requires a few concepts to be defined so let’s go through them one by one.
The runtime for this is a bit tricky so do try to stick with me as we go through this.
Pre-requisites
Before starting on the rest of this article, I highly suggest going through our previous articles on
Algorithmic Complexity - to understand what Big O Notation is
Binary Search Trees - to understand why a heap is not a binary search tree even though it looks like one
Arrays - to understand how index notation works when we use an array to represent our heap
Heaps Part I - to understand a bit of the context behind today’s article
Heaps Part II - to understand the exact operations that we’re working to find the time complexity of
Max Heapify Algorithm Swaps
Let’s go through a recap of the max-heapify algorithm one more time. Let’s assume we have the following binary tree of elements which we started with earlier.
This tree has a height which we’ll call h. In this case, it’s going to be 2.
Definition : The height of a heap is the number of edges between the longest downward path between a node and a leaf
We perform our operation only on non-leaf nodes since leaf nodes are valid heaps by default . If we encounter a leaf node (Eg. node 2 ), we simply move on to the next node. We can do so by performing two calculations to find the left and right child indexes, and determining if they fall within our heap.
But what if we encounter a non-leaf node? Well, then the number of swaps required will simply be equal to the level of the node.
We can see here that the nodes highlighted in blue above have a level of 1. If we wanted to balance the heap containing 2,4 and 3, we would need at most one swap.