Implementing Heaps in JavaScript - Bits and Pieces

Most of the programming languages support some specific data types, for example, `int`

, `string`

, `boolean`

, etc. We can define our custom data type for storing groups of data and this data type can also have functions/operations. These functions/operations can be applied to the data points to get meaningful results. The logical model for the custom data type is called *Abstract Data Type (ADT)* and the physical implementation of these types is called a D*ata Structure*. Data Structures are the most fundamental unit in computer science and it is very important to use the correct data structure for solving problems efficiently. Some of the popular data structures are *Arrays*, *Stacks*, *Queue*, *LinkedList*, *Trees*, *Heaps*, etc. Unlike other high-level languages, most of these data types don’t come bundled with the native JavaScript runtime.

In this article, we’re going to look at one of the interesting data structures — Heaps!

Heaps data structure, unlike Object, Map, and Set is not supported natively in JavaScript.

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

Use **Bit**** **to** **easily publish, install and update small individual modules across different JavaScript projects. Don’t install entire libraries and don’t copy-paste code, when you can build faster with small reusable modules. Take a look.

## 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 `23`

and `36`

while `23`

and `36`

are smaller than their respective child nodes.

In *MaxHeap*, the root node `57`

is greater than its two child nodes `38`

and `45 `

while `38`

and `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 `n`

elements:*Access the min/max value*: `O(1)`

*Inserting an element*: `O(log n)`

*Removing an element*: `O(log n)`

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 `1`

and `2`

. And, then I’ve added the child nodes of `23`

–`32`

& `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 `O(1)`

time.

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 `2`

*i + 1** and 2*

`i + 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 `MinHeap`

class:

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 **O(1)**.*

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.

: Binary Heap is empty and we’d want to insert **insert(10)**`10`

as the first node. `10`

gets added at the first position. Easy!

: Heaps are filled from left to right. Now, **insert(23)**`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!

: Node **insert(36)**`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.

: Node **insert(18)**`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`

with `10`

. `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 `23`

and `57`

while in the 4th illustration, we’ve swapped `32`

and `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[1] = 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 `leftChildIndex`

and `rightChildIndex`

are also changed as:

`leftChildIndex = current * 2 // i* 2`

rightChildIndex = current * 2 + 1 // i * 2 + 1

The `remove`

method should look easy now! I suggest writing the entire code on your own to have a firm understanding of how operations like `insert`

and `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 `if`

conditions.

## Wrapping Up

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.