Security News
The Dark Side of Open Source
At Node Congress, Socket CEO Feross Aboukhadijeh uncovers the darker aspects of open source, where applications that rely heavily on third-party dependencies can be exploited in supply chain attacks.
js-priority-queue
Advanced tools
Readme
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:
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()
.
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:
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
. 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.
npm install
spec-coffee/
coffee/
until gulp test
says you're donegulp
to update priority-queue.js
and priority-queue.min.js
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.
FAQs
Priority queue data structures
The npm package js-priority-queue receives a total of 21,237 weekly downloads. As such, js-priority-queue popularity was classified as popular.
We found that js-priority-queue demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
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.
Security News
At Node Congress, Socket CEO Feross Aboukhadijeh uncovers the darker aspects of open source, where applications that rely heavily on third-party dependencies can be exploited in supply chain attacks.
Research
Security News
The Socket Research team found this npm package includes code for collecting sensitive developer information, including your operating system username, Git username, and Git email.
Security News
OpenJS is warning of social engineering takeovers targeting open source projects after receiving a credible attempt on the foundation.