Repository files navigation

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 cannpm install js-priority-queue orbower install js-priority-queue.Alternatively, just downloadpriority-queue.js from this directory.

Include it throughRequireJS orBrowserify. Or, to pollute your global scope, insertthis in your HTML:

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

Then write code like this:

varqueue=newPriorityQueue({comparator:function(a,b){returnb-a;}});queue.queue(5);queue.queue(3);queue.queue(2);varlowest=queue.dequeue();// returns 5

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

varcompareNumbers=function(a,b){returna-b;};varqueue=newPriorityQueue({comparator:compareNumbers});

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

varqueue=newPriorityQueue({initialValues:[1,2,3]})

We can implement this with a regularArray. We'll keep it sorted inversely,soqueue.dequeue() maps toarray.pop(). Eachqueue() is asplice(),which rewrites the entire array. This is fast for tiny queues.

An alternative is aBinary Heap: itmodifies just a few array elements when queueing (though each modification hasa cost).

Finally, we can use aB-Heap. It's like abinary heap, except its modifications often occur close together in memory.Unfortunately, calculatingwhere in memory the modifications should occur isslower. (It costs a function call instead of a bit-shift.) So while B-heap isfast in theory, it's slow in practice.

Create the queues like this:

varqueue=newPriorityQueue({strategy:PriorityQueue.ArrayStrategy});// Arrayvarqueue=newPriorityQueue({strategy:PriorityQueue.BinaryHeapStrategy});// Defaultvarqueue=newPriorityQueue({strategy:PriorityQueue.BHeapStrategy});// Slower

You'll see running times like this:

According toJsPerf, thefastest strategy for most cases isBinaryHeapStrategy. UseArrayStrategyin edge cases, after performance-testing your specific data. Don't useBHeapStrategy: it's a lesson that a miracle in C can flop in JavaScript.

The default strategy isBinaryHeapStrategy.

1. Fork this repository
2. Runnpm install
3. Write the behavior you expect inspec-coffee/
4. Edit files incoffee/ untilgulp test says you're done
5. Rungulp to updatepriority-queue.js andpriority-queue.min.js
6. Submit a pull request

I, Adam Hooper, the sole author of this project, waive all my rights to it andrelease it under thePublicDomain. Do with it what youwill.