Priority Queue in vanilla JavaScript

In this tutorial we will discuss what is a priority queue and how to implement one with vanilla JavaScript. The implementation here is in pure Java Script, so we will not include third party components and libraries. I believe that the proposed algorithm is simple and yet fast enough for most uses.

What is a Priority Queue?

Before we go into further implementation details, let’s first discuss what a priority queue is.

In short, priority queues are a type of container that stores a series of data in ascending (or descending) order. The elements in such an abstract container receive a priority. So that data may arrive in a different order, but we fetch from them in a sequential.

The implementation proposal in this article offers a custom comparator that allows to customize the order of retrieval.

Why we may need a priority queue?

We may want to use this type of container for different cases, such as:

Networking
Dijkstra algorithm
Data compression

I recently used it during the development of a fast flood with Watershed.

Priority Queue source code

The snippet below reveals the complete source code of our queue. It uses an array based heap to store our data. This implementation includes some common priority queue methods like: “push“, “pop“, “size” and “empty“.

var PQueue = function(){
	this.nodes = [];
}

PQueue.prototype.push = function(el, comparator){
	var nodes = this.nodes;
	var offset = 0,
		size = nodes.length;
	// Find the "offset" by binary search 
	while (offset < size){ 
		const pos = ((offset + size) >>> 1);
		const diff = comparator(el, nodes[pos]);
		((diff < 0) ? (offset = pos + 1) : (size = pos));
	}
	
	nodes.splice(offset, 0, el);
	return this;
}

PQueue.prototype.pop = function(){
	return this.nodes.pop();
}

PQueue.prototype.empty = function(){
	return (this.nodes.length === 0);
}

PQueue.prototype.size = function(){
	return this.nodes.length;
}

The push method uses binary search to find the correct position of the element based on the comparison function we give it.

Example usage

First it sounds good to define our comparison function:

function cmp(a, b){
	return (a - b);
}

As a second step, we can create the queue object and insert several elements into it:

const queue = new PQueue();
queue.push(5, cmp).push(3, cmp).push(7, cmp);

Now its time to fetch the queue elements like this:

while (!queue.empty()) { 
	console.log("entry: %o", queue.pop()); 
}

And voila, the result is:

entry: 3
entry: 5
entry: 7

For more advanced use cases I recommend you to visit image segmentation with Watershed flooding.

Conclusion

This programming tutorial shows a simple realization of PriorityQueue in vanilla Java Script. The algorithm is simple and uses no external libraries and no dependencies.

To achieve performance, we use binary search as we insert items into the queue. In addition, this implementation allows the use of a custom comparison function (custom comparator).