Building a Binary 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 heaps and the heap sort algorithm for incredibly efficient both in terms of time and space.

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

JavaScript

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

Heap.prototype.parent = function(i) {
	return Math.floor(i / 2)
}

Heap.prototype.leftChild = function(i) {
	return i * 2
}

Heap.prototype.rightChild = function(i) {
	return (i * 2) + 1
}

The first thing we'll do is create a new 'Heap' object that will store 3 things:

  • 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

We'll then create 3 simple helper functions to do basic math and allow the rest of our code to be a little cleaner. The parent function will help us to find the index of a value's parent, and the left and right child functions will help us to find the indexes of a value's children.

JavaScript

Heap.prototype.siftUp = function(i) {
	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.

JavaScript

Heap.prototype.siftDown = function(i) {
	var maxIndex = i
	var left = this.leftChild(i)

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

	var right = this.rightChild(i)
	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 'siftDown' function. 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.

JavaScript

Heap.prototype.insert = function(p) {
	if (this.size == this.maxSize) {
		console.log('Error')
	} else {
		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.

JavaScript

Heap.prototype.extractMax = function() {
	var result = this.H[0]

	// Replace root by last leaf
	this.H[0] = this.H[this.size - 1]
	this.H.pop()

	// Decrease size of heap
	this.size--

	// Sift the new root down
	this.siftDown(0)

	// Return the maximum value
	return result
}

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. This is 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.

JavaScript

Heap.prototype.remove = function(i) {
	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.

JavaScript

Heap.prototype.changePriority = function(i, p) {
	var oldP = this.H[i]
	this.H[i] = p
	if (p > oldP) {
		this.siftUp(i)
	} else {
		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.

JavaScript

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.

Be sure to check out how to take advantage of this new heap object with the efficient heap sort algorithm implementation.

Tweet me @tylerewillis

Or send me an email: