Most of the programming languages support some specific data types, for example,
In this article, we’re going to look at one of the interesting data structures — Heaps!
We’re going to implement heaps from scratch. But first, let’s try to understand what heaps are and what sort of computer science problems can Heaps solve?
Tip: Share and reuse utility and UI components
What is a Heap data structure?
A heap is a tree-based data structure which is an almost complete tree that satisfies the heap property.
A complete tree is a tree in which every level, except possibly the last, is completely filled and all nodes are as far left as possible.
We’ll get to the unknown heap property in a moment. Here’s how a binary heap looks like:
A heap is essentially used to get the highest priority element at any point in time. There are two types of heaps, based on the heap property — MinHeap and MaxHeap.
MinHeap: The parent node is always less than the child nodes.
MaxHeap: The parent node is always greater than or equal to the child nodes.
In MinHeap, the root node
10 is smaller than its two child nodes
36 are smaller than their respective child nodes.
In MaxHeap, the root node
57 is greater than its two child nodes
45 are greater than their respective child nodes.
Why do we need something like Heaps?
Heaps is primarily used for getting the minimum or the maximum value present in a heap in
O(1) time. The linear data structures like Arrays or LinkedList can get you this value in
O(n) time while non-linear data structures like Binary Search Trees(BST) can get you this value in
O(log n) time where
n is the number of elements.
Here’s the time complexity of various operations performed on a heap with
Access the min/max value:
Inserting an element:
Removing an element:
Heaps make it blazing fast to access the priority-level elements. The Priority Queue data structure is implemented using Heaps. As the name suggests, you can access elements on a priority basis in
O(1) time using a Priority Queue. It is commonly used in Dijkstra’s Algorithm, Huffman Coding. Don’t worry if you don’t know these algorithms yet! We’ll cover them in detail in the next set of articles.
Heaps helps in quicker access to the min/max elements. Got it! But why do we need these elements in the first place?
Here are some of the real-world use-cases of Heaps:
1. The Operating System uses heaps for scheduling jobs on a priority basis.
2. The producer-consumer model can be implemented using heaps to let consumer access the higher priority elements first. It is used in the implementation of Blocking Priority Queue.
3. Other applications include Order Statistics to find the kth-smallest/kth-largest element in an Array, in HeapSort Algorithm and Graph Algorithms such as Djiktra’s to find the shortest path and Prim’s minimal spanning tree algorithm.
How to implement Heaps?
We represent heaps as sort of trees but they’re not stored as trees in the memory. Let’s try to convert the heap representation in an array and see how it turns out:
Please note the order in which I’ve added the elements in an array. The element
10 is at position
0 and its two children are at position
2. And, then I’ve added the child nodes of
38 and after these nodes, the child nodes of
36 are added. I’ve added the elements level by level. Same goes for the MaxHeap!
But why we follow this particular arrangement of filling the array level by level?
If you carefully observe, the minimum and the maximum elements are placed at the
0th index in their respective arrays. We can access these elements in constant
If a parent is at
0th index, its two child nodes are at
1st and the
2nd position in the array. Here’s the relationship between the parent and the child nodes in a binary heap:
From the above image, we can deduce that the child nodes of any element at index
i are placed at indexes
2i + 1 and
2i + 2. Also, we can go reverse and find out the parent node of any element at
i using the formula
i/2. Please note: this is applicable only for Binary Heaps.
Heaps can be implemented using Arrays or LinkedList but the common way of implementing them is by using Arrays. Now, let’s get to the interesting bit and start implementing Heaps!
We’re going to implement
MinHeap and it will have methods for accessing the min element, inserting a new element and removing an element from the heap. Let’s start by creating a
There’s nothing much going on here! I’ve created an array
heap and initialized it with
null at the
0th index; the actual heap will start getting filled from the
1st index. This is done just to make things easy to understand.
getMin is a simple function that returns the very first element in the heap.
Time Complexity of accessing the min/max element in the heap is
As mentioned earlier, heaps are complete trees except for the last level. The new nodes are inserted from left to right and the heap property is maintained on every insertion. Let’s see this in action:
The above image clearly explains the insertion in Binary Heaps but let me put it into words for better understanding.
insert(10): Binary Heap is empty and we’d want to insert
10 as the first node.
10 gets added at the first position. Easy!
insert(23): Heaps are filled from left to right. Now,
23 gets added as the left child of
10. And since
10 (parent node) is already less than the child node, we don’t have to do anything more here!
36 gets added as the right child of
10. We don’t have to shuffle any nodes here as the minHeap property is already taken care of.
18 gets added as the left child of
23 and this disturbs the minHeap property — The child nodes should be less than the parent node. Now, we go up the chain and find a suitable place for node
18. We start by comparing it with its parent node
23 and since
18 is less than
23, these two nodes are swapped. Now we compare
18 is greater than
10 which means it is at the correct position in the heap.
And that’s how we insert a new node in a Binary Heap! Let’s write some code to implement the insert function:
The above code shouldn’t be difficult to understand! We start by adding the new node at the end of the array (Remember, a heap is a complete tree except for the last level and it gets filled from left to right).
And now we keep checking the current element with that of its parent. The current node and the parent node are swapped if the current node is smaller than its parent. Please note: the index of the current node is
current and that of its parent is
current/2. We’re using ES6 Array destructuring syntax to swap these two elements. The process of balancing the heap after inserting or removing an element is called heapify. When we traverse up the heap to find a suitable place for the new node, it is commonly called heapifyUp.
The time complexity of inserting a new element in a binary heap is
O(log n) where
n is the number of elements. The number of elements to compare gets reduced to half on every iteration and hence
log n .
Now let’s see what happens when we remove an element from the heap:
Here, we’re removing the minimum node
10 from the binary heap. When the root node is removed, the extreme right node (
57) comes at the position of the root node. You can see this in the second illustration that the node
57 becomes the root node. We’ll have to restore the minHeap property.
We start traversing down the heap and check if the child nodes are smaller than the parent. If any of the child nodes is smaller than the parent, we swap the parent with the smallest child node.
Please note in the 3rd illustration, we’ve swapped
57 while in the 4th illustration, we’ve swapped
57. The 4th illustration is now a valid minHeap!
Let’s implement the remove function. It’s a bit difficult! Please go through the illustrations once and understand who is getting shifted where and why!
Here’s the code for the remove function:
We first store the minimum element at index
1 in the variable
smallest. We’ll have to check for the minHeap property if the size of the heap is greater than
2. If the size of the heap is
2, we don’t have to check anything. We’ll simply remove the element at index
1 using the
splice function. You can see this bit in the
else if block.
Now, let’s get onto the humongous
if block which is doing the majority of the work. We first put the last element at index
1 and then remove the last element from the heap as:
this.heap = this.heap[this.heap.length-1]
this.heap.splice(this.heap.length - 1)
It is easy to retain the heap property if there are only
3 elements remaining in the heap. We simply swap the smallest element with the root node. That is it!
If there are more than 3 elements, we traverse down the heap to find a suitable place for the root node. The process of traversing down the heap is commonly called heapifyDown.
The condition in the while block looks big but it is not doing much! It simply checks if the current element is smaller than both of its child nodes. Then the smallest child node and the parent node are swapped and the
current variable is changed accordingly.
The values of
rightChildIndex are also changed as:
leftChildIndex = current * 2 // i* 2
rightChildIndex = current * 2 + 1 // i * 2 + 1
remove method should look easy now! I suggest writing the entire code on your own to have a firm understanding of how operations like
remove are implemented in binary heaps.
Here’s the complete code for implementing MinHeap:
Try writing the code for MaxHeap on your own. It should not be difficult, you just have to tweak a few
We learned that the Heaps data structure is an almost complete tree that satisfies the heap property. We can access the min/max elements in
O(1) from the heap. We can implement Priority Queue using heaps which are essentially used for accessing the elements on a priority basis. In the next article, we’ll look at some of the popular interview questions on heaps.