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:

<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 thecomparator option.This is the argument we would pass toArray.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'sfaster 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 regularArray. We'll keep it sorted inversely,soqueue.dequeue() maps toarray.pop().

But with anArray, we'll need tosplice(), which can affect every singleelement in the array. An alternative is to create aBinary Heap, which writes farfewer array elements when queueing (though each element is written more slowly).

Finally, we can use aB-Heap. It's like abinary heap, except it orders elements such that during a single operation,writes occur closer to each other in memory. Unfortunately, it's slower tocalculate where in memory each write should occur (it costs a function callinstead of a bit-shift). So while it's fast in theory, it's slower in practice.

Create the queues like this:

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

You'll see running times like this:

According toJsPerf, thefastest strategy for most cases isBinaryHeapStrategy. Only useArrayStrategyonly if you're queuing items in a very particular order. Don't useBHeapStrategy, except as a lesson in how sometimes miracles in oneprogramming language aren't great in other languages.

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.