Skip to content

Priority queue in 26 lines (863 bytes): gusset-dampeningly small and fast ๐Ÿ’…

License

Notifications You must be signed in to change notification settings

alanmacleod/nanoq

Folders and files

NameName
Last commit message
Last commit date

Latest commit

ย 

History

34 Commits
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 

Repository files navigation

Build Status License: MIT

nanoq

The world's fastest Javascript priority queue? Maybe?

Itsy bitsy teeny weeny priority queue implemented as a blazing fast binary heap in fewer than 30 lines of code (sort of .. ok there's a couple of lines with two statements).

Supports arbitrary objects including strings or, by passing a maximum tree size, will select the best TypedArray for guaranteed compact memory usage (...won't somebody think of the mobiles T_T)

Benchmarks

ran under Node v6.9.1

package num items (push/pop) time (seconds)
nanoq (v0.0.3) 10,000,000 1.855 ๐Ÿ”ฅ
tinyQueue (v1.2.2) 10,000,000 2.714
FastPriorityQueue (0.2.4) 10,000,000 12.008

Usage

nanoq has four methods; push(), pop(), peek() and length(), all fairly self-explanatory oui?

Install via npm:

$ npm install nanoq
var nanoq = require('nanoq');

// nanoq is a "minheap" by default
var q = new nanoq();

q.push(30);
q.push(20);
q.push(10);

console.log(q.length()) // returns 3. length() is a method not a property
console.log(q.pop(), q.pop(), q.pop()); // returns 10, 20, 30

// Works with strings:
q = new nanoq();

q.push("dog");
q.push("pig");
q.push("cat");

// peek() returns the topmost item without pop()ing
console.log(q.peek()) // returns "cat"

// force a TypedArray by passing in a maximum number of heap items
q = new nanoq(255);
// Note: .push() accepts integers only in this mode

// use your own comparator, here is a maxheap
// (pass 0 or null for the 1st param if you want to use regular JS arrays)
q = new nanoq(null, function(a,b) {
  return a < b;
});

// add items to the maxheap
q.push(1);
q.push(2);
q.push(3);

console.log(q.pop(), q.pop(), q.pop()); // returns 3, 2, 1

// use your own custom objects
var stuff = [
    {val: 3},
    {val: 2},
    {val: 1},
];

q = new nanoq(null, function(a, b){
  return a.val > b.val
});

for (var s of stuff)
  q.push(s);

console.log(q.pop(), q.pop(), q.pop()); // returns {val:1}, {val:2}, {val:3}

About

Priority queue in 26 lines (863 bytes): gusset-dampeningly small and fast ๐Ÿ’…

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published