Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More
Socket
Sign inDemoInstall
Socket

js-priority-queue

Package Overview
Dependencies
Maintainers
1
Versions
9
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

js-priority-queue

Priority queue data structures

  • 0.1.5
  • latest
  • Source
  • npm
  • Socket score

Version published
Weekly downloads
26K
increased by4.23%
Maintainers
1
Weekly downloads
 
Created
Source

Priority Queue

A priority queue is a data structure with these operations:

OperationSyntax (js-priority-queue)Description
Createvar queue = new PriorityQueue();Creates a priority queue
Queuequeue.queue(value);Inserts a new value in the queue
Lengthvar length = queue.length;Returns the number of elements in the queue
Peekvar firstItem = queue.peek();Returns the smallest item in the queue and leaves the queue unchanged
Dequeuevar firstItem = queue.dequeue();Returns the smallest item in the queue and removes it from the queue
Clearqueue.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:

<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

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().

But with an Array, we'll need to splice(), which can affect every single element in the array. An alternative is to create a Binary Heap, which writes far fewer array elements when queueing (though each element is written more slowly).

Finally, we can use a B-Heap. It's like a binary heap, except it orders elements such that during a single operation, writes occur closer to each other in memory. Unfortunately, it's slower to calculate where in memory each write should occur (it costs a function call instead 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 }); // Array
var queue = new PriorityQueue({ strategy: PriorityQueue.BinaryHeapStrategy }); // Default
var queue = new PriorityQueue({ strategy: PriorityQueue.BHeapStrategy }); // Slower

You'll see running times like this:

OperationArrayBinary heapB-Heap
CreateO(n lg n)O(n)O(n)
QueueO(n) (often slow)O(lg n) (fast)O(lg n)
PeekO(1)O(1)O(1)
DequeueO(1) (fast)O(lg n)O(lg n)

According to JsPerf, the fastest strategy for most cases is BinaryHeapStrategy. Only use ArrayStrategy only if you're queuing items in a very particular order. Don't use BHeapStrategy, except as a lesson in how sometimes miracles in one programming language aren't great in other languages.

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.

Keywords

FAQs

Package last updated on 22 Feb 2016

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc