Building a Binary Max Heap in JavaScript

Use Case:

Binary heaps are data structures in computer science that allows for a program to both insert into and extra the max value from efficiently - in O(log n) time. This is favorable to JavaScript arrays where values can be pushed to the back of the array in O(1), or constant time, but retrieving the maximum value would be measured in O(n) - or linear time.

For this reason alone, binary heaps may not make sense for your program. However, for sorting purposes, binary max heaps and the heap sort algorithm for incredibly efficient both in terms of time and space.

Below is my implementation for building a binary max heap in JavaScript which we'll use the implementation of in my next post on the heap sort algorithm.

1. Creating a Heap Class

class Heap {

	constructor(maxSize) {
		this.size = 0
		this.maxSize = maxSize
		this.H = []
	}

	parent = i => Math.floor(i / 2)
	leftChild = i => i * 2
	rightChild = i => (i * 2) + 1

The first thing we'll do is create a new class called Heap that will store 3 elements:

• The current size of our heap
• The allowable max size of our heap (that we'll get from the parameter)
• An array of the values in our heap

All remaining code in this post will be within our Heap class.

We should note that the values in our heap will be held in an array called H which, while an array data structure, will actually be used and treated like a binary tree. This will allow us to be more efficient in terms of memory since we won't be worried about storing parent and children nodes and pointers.

Instead of storing these values, our tree will be created on the fly with the parent, leftChild, and rightChild functions that will perform simple math operations leveraging the index values of the array to determine the parent and child nodes. Refer to my previous post on using arrays as binary trees to see a greater explanation.

2. siftUp Function

siftUp = i => { // O(log n)
	while (i > 0 && this.H[this.parent(i)] < this.H[i]) {
		var temp = this.H[this.parent(i)]
		this.H[this.parent(i)] = this.H[i]
		this.H[i] = temp
		i = this.parent(i)
	}
}

Then we'll declare a function called siftUp that we'll use to move an element up in our array. We'll need this when we insert new values (to move the new value into the proper place in our binary max heap), remove values and change value priorities.

Here we'll loop through our heap array until either the parent is greater than the value or we've reached the first index - 0. Along the way we'll swap our current value with the existing value based on index.

3. siftDown Function

siftDown = i => { // O(log n)
	var maxIndex = i
	var left = this.leftChild(i)
	var right = this.rightChild(i)

	if (left <= this.size && this.H[left] > this.H[maxIndex]) {
		maxIndex = left
	}
	if (right <= this.size && this.H[right] > this.H[maxIndex]) {
		maxIndex = right
	}

	if (i !== maxIndex) {
		var temp = this.H[i]
		this.H[i] = this.H[maxIndex]
		this.H[maxIndex] = temp
		this.siftDown(maxIndex)
	}
}

There are times that we'll need to move a value down as well, so we'll create a function called siftDown. This will be particularly useful when we remove and return the maximum value in our heap.

In order to do this, we'll take our starting index value (which we know won't be any greater than it is currently - thus maxIndex), and use it look to the child on the left and the child on the right. If the child is bigger, we'll take the biggest one and declare that as our new maximum index.

As long as our original and max indexes don't match, we'll swap the values and then recall the function. In this case, the 'siftDown' function is a recursive function.

4. insert Function

insert = p => { // O(log n)
	if (this.size !== this.maxSize) {
		this.H[this.size] = p
		this.siftUp(this.size)
		this.size++
	}
}

To insert new values into our heap, we'll first need to check to be sure we haven't reached the maximum allotted size. If not, we'll create a new index that will hold the value, call the 'siftUp' function on the index to move it into its proper place, and increase the current size of the heap.

5. extractMax Function

extractMax = () => { // O(log n)
	var result = this.getMax()
	this.H[0] = this.H[this.size - 1] // replace root by last leaf
	this.H.pop() // remove last leaf
	this.size-- // decrease size of heap
	this.siftDown(0) // sift the new root down
	return result // return the maximum value
}

Extracting the maximum value in our heap is perhaps one of the main reasons that we're creating our heap to begin with. Here, using our extractMax function, we're setting the variable result equal to the array value located in the first index - 0 by leveraging a new function called getMaxthat will return our current maximum value.

Now, we could just return the maximum value and we'd have it, but it's also important (for algorithmic purposes related to heap sort) that we also remove the item. When we do this, we need to replace it with something, so we'll look to the end of our heap and replace the maximum with that value.

Then, we'll remove the value at the end of our heap, reduce the size of the current heap, and call our 'siftDown' function to put the value we just moved forward into its proper location.

6. getMax and getSize Functions

getSize = () => this.size // O(1)

getMax = () => this.H[0] // O(1)

We'll introduce 2 1-line functions that will each return a single value. The getSize function will give us the current size of our heap which is a stored variable belonging to the Heap class and is updated every time we add or remove new values. Then, our getMax function allows us to get the current maximum value in our heap without removing it.

7. remove Function

remove = i => { // O(log n)
	this.H[i] = Infinity
	this.siftUp(i)
	this.extractMax()
}

There are times when we may want to remove values from our heap, so we can do that with our remove function that will set the current index value to infinity (ensuring that it will be the new max value), call the 'siftUp' function to move the item to the top, and then call the 'extractMax' function to remove it.

8. changePriority Function

changePriority = (i, p) => { // O(log n)
	var old = this.H[i]
	this.H[i] = p
	var result = (p > old) ? this.siftUp(i) : this.siftDown(i)
}

Other functionality that we may need would be the ability to change a value (or a value's priority). When we do this, we'll then need to put it in it's proper place so we'll either siftUp or siftDown depending on if the new value is greater than the previous value or not.

9. Results

var heap = new Heap(10)
heap.insert(5) // 5
heap.insert(6) // 6,5
heap.insert(3) // 6,5,3
heap.insert(7) // 7,6,3,5
heap.insert(2) // 7,6,3,5,2
heap.insert(8) // 8,7,6,5,2,3
heap.extractMax() // 7,6,3,5,2
heap.changePriority(2, 9) //9,7,6,5,2
heap.remove(3) //9,7,6,2

Once entire heap object is built, we can go ahead and declare a new heap, insert values into it, extract the maximum value, change a value's priority, or remove a value outright.

As noted in the code examples, each of the above functions can be done in logarithmic time - O(log n) - except for the 2 get functions that can be done in constant time - O(1). While data structures being able to perform multiple basic operations in logarithmic time is notably efficient, most operations would be constant time except for the need to abide by our ordered "max heap" rules. But having our heap ordered by maximum value will allow us to perform a sorting algorithm in O(n log n) which is the topic of my next post on the heap sort algorithm.