js-priority-queue

by adamhooper

adamhooper / js-priority-queue

Priority queues in JavaScript

208 Stars 35 Forks Last release: Not found Other 35 Commits 11 Releases

Available items

No Items, yet!

The developer of this repository has not created any items for sale yet. Need a bug fixed? Help with integration? A different license? Create a request here:

Priority Queue

A priority queue is a data structure with these operations:

| Operation | Syntax (js-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.

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.

Installing

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:


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

Strategies

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:

| Operation | Array | Binary heap | B-Heap | | --------- | ----- | ----------- | -------------- | | Create | O(n lg n) | O(n) | O(n) | | Queue | O(n) (often slow) | O(lg n) (fast) | O(lg n) | | Peek | O(1) | O(1) | O(1) | | Dequeue | O(1) (fast) | O(lg n) | O(lg n) |

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
.

Contributing

  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

License

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.

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.