A priority queue is a data structure with these operations:

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

Why use this library? Two reasons:

1. It's easier to use than an Array, and it's clearer.
2. It can make your code execute more quickly.

You can npm install js-priority-queue or bower install js-priority-queue. Alternatively, just download priority-queue.js from this directory.

Include it through RequireJS or Browserify. Or, to pollute your global scope, insert this in your HTML:

<script src="priority-queue.js"></script>

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

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({ initialValues: [ 1, 2, 3 ] })

We can implement this with a regular Array. We'll keep it sorted inversely, so queue.dequeue() maps to array.pop(). Each queue() is a splice(), which rewrites the entire array. This is fast for tiny queues.

An alternative is a Binary Heap: it modifies just a few array elements when queueing (though each modification has a cost).

Finally, we can use a B-Heap. It's like a binary heap, except its modifications often occur close together in memory. Unfortunately, calculating where in memory the modifications should occur is slower. (It costs a function call instead of a bit-shift.) So while B-heap is fast in theory, it's slow in practice.

Create the queues like this:

var queue = new PriorityQueue({ strategy: PriorityQueue.ArrayStrategy }); // Array
var queue = new PriorityQueue({ strategy: PriorityQueue.BinaryHeapStrategy }); // Default
var queue = new PriorityQueue({ strategy: PriorityQueue.BHeapStrategy }); // Slower

You'll see running times like this:

According to JsPerf, the fastest strategy for most cases is BinaryHeapStrategy. Use ArrayStrategy in edge cases, after performance-testing your specific data. Don't use BHeapStrategy: it's a lesson that a miracle in C can flop in JavaScript.

The default strategy is BinaryHeapStrategy.

1. Fork this repository
2. Run npm install
3. Write the behavior you expect in spec-coffee/
4. Edit files in coffee/ until gulp test says you're done
5. Run gulp to update priority-queue.js and priority-queue.min.js
6. Submit a pull request

I, Adam Hooper, the sole author of this project, waive all my rights to it and release it under the Public Domain. Do with it what you will.