How to Create a Heap Data Structure in JavaScript

4 min readFeb 27, 2021

Welcome to heaps. Heaps have a binary search tree like structure. Each parent node has two children nodes that all stem from a root. Heaps can be ordered in two ways:

Max Heap: A max heap will have their biggest value as the root and the value of each parent node is always greater than its child nodes.

Min Heap: A min heap will have their smallest value as the root and the value of each parent node is always smaller than its child nodes.

Heaps have no implied ordering between siblings. The bigger one can be the left child node or the right child node, it does not matter. A heap is as compact as possible. All the children of each node are as full as they can be, and left children are filled out first.

Implementation

For the rest of this article, we will focus on the max heap. We can implement the max heap above using an array.

[30,22,27,16,11,23,9]

We can see our root is at index 0 and its child nodes are at index 1 and 2. How do we know which indexes are the child nodes to nodes at index 1 and 2?

For any i-th index of an array:

The left child is stored at 2 * i + 1 index.
The right child is stored at 2 * i + 2 index.
For any child node at index i, its parent nodes is at floor((i-1)/2) index.

Insertion

We will use our heap from earlier and we will try to insert a new node with a value of 32.

[30,22,27,16,11,23,9,32]

Our new node is added to the end of the array. That is nowhere close to where we want this node to be. This node is the biggest node in the entire array. We can use the bubble technique to get our new value into the right place. We compare 32 to its parent node 16. We see that 32 is much bigger than 16, so we want to switch places of the two nodes. Our array now looks like:

[30,22,27,32,11,23,9,16]

We continue this pattern of comparing and swapping our node and the parent node until we find a parent node that is bigger than our node. This process is called bubbling up. Our final heap will look like:

[32,30,27,22,11,23,9,16]

What does this look like in code:

Removing the biggest element

In our max heap, we have our largest element being the root. We will have to shift our entire tree upwards to restore our heap. Let’s go back to our initial max heap:

We take out our root and swap it with our last value in our heap (the rightmost node). 9 is the new root. Our new array looks like:

[9,22,27,16,11,23]

We must order the heap by bubbling down. We compare our node to the left and right child node and see which one is the greatest. 9 is obviously smaller than 22 and 27. 27 is the greater of the two, so we want to swap places for 9 and 27. The array now looks like:

[27,22,9,16,11,23]

Our 9 node is still not in the right place. We keep comparing and swapping our node until its child nodes are smaller than it. Our final heap will look like:

[27,22,23,16,11,9]

What does this look like in code:

There are ways to reorganize the heap recursively that some of my resources go over.

Big O

Insertion — O(log N)

Removal — O(log N)

Search — O(N)

Next article, we will go over a priority queue. Priority queue is one of the most useful implementations of a heap. For a little sneak peak, a priority queue is a data structure where each element has a priority. Elements with higher priorities are served before elements with lower priorities.

Resources

For more resources on Heaps, I suggest looking at these helpful links.

Cool visualization of a heap: https://visualgo.net/en/heap

https://medium.com/swlh/data-structures-heaps-b039868a521b

https://medium.com/basecs/learning-to-love-heaps-cef2b273a238

https://medium.com/basecs/heapify-all-the-things-with-heap-sort-55ee1c93af82

udemy.com/course/js-algorithms-and-data-structures-masterclass/learn/lecture/8344810#overview