Implementing a Max Heap in JavaScript

Photo by Tyler Milligan on Unsplash

Last week I wrote about implementing quicksort in JavaScript, the next sorting algorithm I would like to cover is heap sort. However, in order to do so, we need to understand the heap data structure. A heap is a tree based structure. Specifically we will be looking at a max heap, which is a form of binary heap that satisfies the heap property. The heap property states that every child node will be less than (or greater than, in the case of a min heap) its parent node. This means that the root node will always be the maximum element in the heap, and each node thereafter will have at most 2 child nodes. A max heap is also a complete binary tree, which means that each level must be filled before moving to the next, and that if a level is not full, the leaves (nodes on a tree with no children) must be positioned as far left as possible.

Max Heap

Max heap visualization

Note: through out this blog I’m going to be using 0 based indexing, it is common to use 1 based indexing when dealing with heaps.

Initially, one might think to implement a max heap using nodes with pointers, as you might implement a binary search tree. However, the power of a heap, comes from using an array structure instead. Using some simple formulas, we can determine the parent, left child, and right child of elements in the array.

First let’s come up with a formula to find the left and right children.

left child = (index * 2) + 1

right child = (index * 2) + 2

How does this work? Well, starting from our root node at index 0.
0 * 2 = 0
left child = 0 + 1
right child = 0 + 2

We can see this coincides with our visualization. The root node’s children are at indices 1 and 2 in the array.

How about for the node at index 1?
1 * 2 = 2
left child = 2 + 1
right child = 2 + 2

Again, this aligns with our visualization, where the left and right children are at positions 3 and 4.

Now to come up with the formula for deriving the index of the parent node:

parent = floor( (index - 1) / 2 )

Let’s find the parent node for the element at index 4

floor( (4 - 1) / 2 ) → floor(3 / 2) → floor(1.5) → 1

It works! Now that we know how to find the children and parent elements, let’s start coding and figure out how to build a max heap in JavaScript.

Code

Let’s create our class.

From here on out, all of the code will go inside of this class. We’ll start with the methods to derive the indices of children and parent nodes

Now we’re going to make a method to determine if a given node is a leaf. A leaf is a node that doesn’t have any children. In a complete binary tree, the number of leaves is (number of nodes + 1) / 2. We can use that to our advantage, to find the index of the first leaf. We can use the length property of our values array to get the correct starting index of the leaves. The leaves will go from this index until the index of the last element in our array.

We’re going to be doing a lot of swapping of elements, to maintain the heap property of our max heap, so let’s create a method to swap two elements in the values array.

Now we need to be able to add elements to our heap.

We will start by adding the element to the end of our values array. After that we need to move the element up the heap until it is in its correct position. We broke the last bit of code into its own method, heapifyUp.

The process is pretty simple, since we have a method to give us the index of a node’s parent element. Starting with the current element, we compare its value to the value of its parent. If it is greater than the parent, since this is a max heap, we know we need to swap those elements. After we swap, the current index is now at the index of the parent, and there is a new parent node to compare to. We will do this until the node is not greater than its parent and therefor satisfies the heap property, or until it is the root node.

One of the most common implementations of a max heap is a priority queue. Which is a data structure that allows an element to be given a priority, the element with the highest priority is returned before all other elements. In a max heap, the maximum element is the root node or first element. We can remove it using extractMax().

The way we do this is by getting the value of the first element to return, moving the last element to the first position, and the moving it down the heap until it is in its correct position again (as to satisfy the heap property). We use a method to called heapifyDown to move the element down the heap into its correct position.

The first thing we do is check to make sure the element isn’t a leaf (because if it doesn’t have any children then there is no way for it to move down any further). After that we check to see if it is less than either of its children, if so, it needs to be swapped with the child that has the greatest value. If it has been swapped, we need to recursively call heapifyDown, giving it an argument of the element’s new index (which is the index of the child it just swapped with).

Since we can use heapifyDown, now we can take in an array and turn it into a max heap!

This works, because we work from the leaves up, pushing each element down to its correct location in the heap, until we reach the root node.

Now for a simple method peek() which will just return the value of the max element in the heap.

Finally, we will write a method to print out our max heap.

This works by starting with the root node, and printing out each element and its left and right child, until it gets to the leaves of our binary heap.

Time and Space Complexity

Time Complexity

Let’s look at the time complexity of the methods we just wrote:

• leftChild, rightChild, parent, and isLeaf() take O(1) time
• heapifyUp, and heapifyDown both take O(log n) time
• add takes O(log n)
• extractMax takes O(log n) time
• print takes O(n-l) where l represents the number of leaves. In a complete binary tree, 1/2 the nodes are leaves, so you could also say O(1/2n) or simply, O(n).
• buildHeap takes O(n)

heapifyUp and heapifyDown technically take O(h), where h is the height of the heap, however, complete binary trees have a height of ceil(log2(N+1)) - 1. This makes sense because worst case an element either gets pushed from the bottom to the top, or from the top to the bottom, going level by level.

The answer to this stack overflow question, is very detailed as to why buildHeap takes O(n) time. To simplify it and put it in my own words, it takes linear time, because:

1. At the bottom level, the leaves can not be pushed down any further
2. At the second most bottom level, the nodes can at most be pushed down one level
3. At the third most bottom level, the nodes can at most be pushed down two levels
4. As we move up the heap, they can each be pushed down further, but there are less nodes

There are more nodes at each level, but the maximum time that heapifyDown can take, decreases (because as mentioned, heapifyDown actually takes O(h) where h is the height of the heap). So rather than O(n log n), it amounts to O(n).

Space Complexity

Space complexity of a max heap is O(n). We only have our values array, and move elements around within this array.

In Conclusion…

Learning about heaps was interesting, I would have never thought to use an array to represent a binary tree. Not only will it be useful to learn heap sort, but also they have other use cases like being used for a priority queue. The code in this blog can be found in this GitHub repository. If you would like to see a visualization of a max heap, and some of its methods, you can go here.