Apologies to anyone who might have received a new email today called What to Expect from this newsletter - I was editing some things in my first newsletter Article and accidentally sent it out.
Welcome Back to Think Like A Programmer, where we break down complicated computer science concepts into bite-sized articles for you.
In today’s article, we’ll continue looking at 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
Why use a heap?
How to add items to an existing heap
How to remove items from an existing heap
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
So, what’s left for us to go through with heaps?
The short answer is that we’re left with 2 big concepts pertaining to heaps
How to represent a heap in memory
How to construct a heap from a list of elements from scratch?
We’ve gone through a few different data structures in the past few weeks, but not all of them will be appropriate for us to reap the benefits of a heap. Let’s go through them one by one.
Can we use a Linked List? If you’ve forgotten what these are, you can read our article on linked lists here.
Immediately, a glaring problem jumps out at us - our heap parent nodes have two children each, but our linked list nodes only have space for …. 1 ? That means that we won’t be able to use our linked lists at all for heaps.
The same problem applies when we stretch for Stacks and Queues - these all have capacity for at most 1 child or none.
Well, how about using a binary search tree then? That way, each node can have 2 children.
While that does indeed solve our original problem of having enough space to store a reference to 2 children, we have a new problem - finding any element takes at worst O(n) time since we never have a guarantee that our binary search tree is balanced.
If you’re not sure why the worst case scenario is O(n) , revisit our article on Binary Search Trees here. If you’re not sure what O(n) is, then revisit our article on Algorithmic Complexity here.
This means that even before we can perform our insertion or deletion algorithm, we already incur a cost of O(n) steps at worst.
So, what’s the solution here? Surprisingly, it’s an array - or an dynamic array if you want a heap to be unbounded in size.
Let’s build some intuition for why this might be the case.
Heaps
Indexing Heaps
If you’ve forgotten what a heap looks like, here you go.
Quick Recap : Is this a max heap or a min heap? Don’t scroll down until you’ve made a guess as to what it might be
The answer is that, it’s a min heap! This is because of two reasons
Order : All parent nodes are smaller than or equal to their child nodes
Shape : All levels, except for the last level, are completely filled.
As a result, we have a min heap. If we were to index the elements from 0, starting from the root node, we would get the following indexes.
Interestingly, if we have the index of a parent node, we can calculate the indexes of its left and right child using the formula seen below. Note that i is the index of the parent node.
left = 2*i + 1
right = 2*i + 2We can verify this is the case by trying a few examples
Parent = 0
left = 2 * 0 + 1 = 1
right = 2 * 1 + 2 = 2
parent = 1
left = 2 * 1 + 1 = 3
right = 2 * 1 + 2 = 4