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 be looking at heaps - which are used to find the maximum or minimum elements of a list of elements in the fastest time.
This sounds very … limited and you’re not exactly wrong if you think that way. When I first learnt about heaps, I thought that they were rather useless. After all, why care about finding the maximum or minimum element in a list of elements when we could just sort the list or just traverse the list to find the largest/smallest element.
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
So, why use heaps?
The short answer to that is heaps can help us find a maximum and minimum element in a constant amount of time - since this is always the root node. Even when we add in a new element or delete existing ones, we will only need O(log(n)) time to rebalance the heap.
Fun Tidbit : I found this interesting Quora answer when trying to find some real-life applications of heaps : https://www.quora.com/What-are-some-real-world-applications-of-a-heap-data-structure, worth a look!
If we were to use a traditional array or linked list, we would have to use O(n) since we would need to go through every element in the array, perform a comparison. When we add or delete elements in our array, this runtime doesn’t change.
Here’s a quick graph to visualise the difference between log(n) and n as the size of n increase from 0 to 1000 elements. It’s quite drastic to say the least, with the difference growing significantly as the number of elements grow.
I hope this has piqued your curiosity about heaps - so without ado let’s start delving into them.
Note : In this article, we’ll be covering binary heaps only. We won’t be covering heaps with more than two child nodes since they are out of scope for this topic and a tad bit more complex and rare.
We’ll be looking at an implementation of a heap using arrays in the following weeks - this week is just a high level overview.
Introduction
Parent Nodes and Child Nodes
Two weeks ago, we covered Binary Search Trees - where we look at the nodes that look like what we have below.
If we were to designate 56 as a parent node, then 30 and 70 would be its child nodes. If we were to blow up our binary search tree and add a few more elements, we can see that there can be multiple parent nodes in the same tree.
This makes sense since parent and child nodes are just terms we use to identify a relationship between individual nodes. This is an important concept to understand.
Applying this to Heaps
So how does this apply to a binary heap?