Priority Queue

A priority queue is a data structure with these operations:

Operation	Syntax (ts-priority-queue)	Description
Create	var queue = new PriorityQueue();	Creates a priority queue
Queue	queue.queue(value);	Inserts a new value in the queue
Length	var length = queue.length;	Returns the number of elements in the queue
Peek	var firstItem = queue.peek();	Returns the smallest item in the queue and leaves the queue unchanged
Dequeue	var firstItem = queue.dequeue();	Returns the smallest item in the queue and removes it from the queue
Clear	queue.clear();	Removes all values from the queue

You cannot access the data in any other way: you must dequeue or peek.

Provides an O(log n) approach to priority queue insertions and removals. I forked this from the CoffeeScript js-priority-queue library so that I could write it in TypeScript. I've removed the array- and BHeap-based strategies as they were not recommended for use anyway.

Installing

You can npm install ts-priority-queue

Then write code like this:

var queue = new PriorityQueue({ comparator: function(a, b) { return b - a; }});
queue.queue(5);
queue.queue(3);
queue.queue(2);
var lowest = queue.dequeue(); // returns 5

Options

How exactly will these elements be ordered? Let's use the comparator option. This is the argument we would pass to Array.prototype.sort:

var compareNumbers = function(a, b) { return a - b; };
var queue = new PriorityQueue({ comparator: compareNumbers });

You can also pass initial values, in any order. With lots of values, it's faster to load them all at once than one at a time.

var queue = new PriorityQueue({ comparator: compareNumbers, initialValues: [ 1, 2, 3 ] })

Complexity:

Operation	Complexity
Create	O(n lg n)
Queue	O(lg n)
Peek	O(1)
Dequeue	O(lg n)

License

Public Domain. Do with it what you will.