mourner / tinyqueue Goto Github PK

View Code? Open in Web Editor NEW

383.0 14.0 45.0 24 KB

The smallest and simplest priority queue in JavaScript.

License: ISC License

JavaScript 100.00%

algorithm javascript priority-queue binary-heap data-structure

tinyqueue's Introduction

tinyqueue

The smallest and simplest binary heap priority queue in JavaScript.

// create an empty priority queue
var queue = new TinyQueue();

// add some items
queue.push(7);
queue.push(5);
queue.push(10);

// remove the top item
var top = queue.pop(); // returns 5

// return the top item (without removal)
top = queue.peek(); // returns 7

// get queue length
queue.length; // returns 2

// create a priority queue from an existing array (modifies the array)
queue = new TinyQueue([7, 5, 10]);

// pass a custom item comparator as a second argument
queue = new TinyQueue([{value: 5}, {value: 7}], function (a, b) {
	return a.value - b.value;
});

// turn a queue into a sorted array
var array = [];
while (queue.length) array.push(queue.pop());

For a faster number-based queue, see flatqueue.

Install

Install using NPM (npm install tinyqueue) or Yarn (yarn add tinyqueue), then:

// import as an ES module
import TinyQueue from 'tinyqueue';

// or require in Node / Browserify
const TinyQueue = require('tinyqueue');

Or use a browser build directly:

<script src="https://unpkg.com/[email protected]/tinyqueue.min.js"></script>

Thanks

Inspired by js-priority-queue by Adam Hooper.

tinyqueue's People

Contributors

Stargazers

Watchers

tinyqueue's Issues

Investigate performance compared to FastPriorityQueue and qheap

https://github.com/lemire/FastPriorityQueue.js
https://github.com/andrasq/node-qheap

Both seem to perform better on some benchmarks. Should investigate what makes them faster.

after pop the order change in queue

Is it a "stable queue" or not?

Hi.

If I insert multiple items which are "equal" (i.e. for which the comparator returns 0), does pop() preserve the order in which the items were push()'ed? (Order preservation is called "stable property", i.e. there are "stable sorts", "stable queues" etc.)

Binary heap is typically not stable - https://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap - so I assume tinyqueue is not stable as well?

It's not mentioned anywhere in the docs...

Incorrect pop

Script and reproduce case below:

TinyQueue = require('./index.js')
q = new TinyQueue()
lpush = function(a) { console.log('push', a); q.push(a) };
lpop = function() { console.log('pop', q.pop());  };

lpush(0);
lpop(); // 0 (correct)

lpush(2);
lpush(5);
lpop() // pop 2 (correct)

lpush(4);
lpop() // pop 2 (should be 4)
lpop() // pop 2 (should be 5)
lpop() // pop undefined (correct)

As I said in another issue I just dropped tinyqueue for another lib, so I won't fix it.
But maybe someone will have fun debugging it.

Bug: down() use a wrong length

For some reason i had to replace some old PriorityQueue I was using in my game (for pathfinding) in favor of a new one.
I wanted something small and it's why I chose tinyQueue.

However after a simple port to another haxe, I had the lib crashing on that line:

  if (right < this.length && compare(data[right], best) < 0) {

The problem is that this.length is decremented after using _down(0), leading to a situation where _down function uses an incorrect length, resulting in data[right] being undefined and crashing the game.

Below you can see when _length get inconsistent, between the data.pop and length--:

  // from pop()
  // [...]
  const bottom = this.data.pop();
  if (this.length > 1) {
    this.data[0] = bottom;
    this._down(0);
  }
  this.length--;
  // [...]

As soon as I moved this.length--; under const bottom = this.data.pop();, problem was fixed.

Note that even if on my haxe app i get an Error, it's probable that it will be silent in JS, as:

JS array can access unexisting key, ex: [][-1] or [][100] will not trigger an error and will be undefined.
comparaison with undefined somehow works, ex: 3 < undefined is false

I'm not remotely sure if that could even be a bug in a running js app, but better be safe than sorry ;).

Package 'module' field is in ES6 syntax -- incompatible with IE

Hi,

I am trying to consume this package with webpack, which will use the module field in package.json.

That module field points to a ES6 version of the package. I believe module should be used for ES6 import / export syntax, but still needs to be runtime compatible with ES5.

This leads to webpack pulling in an ES6 class which causes a syntax error in IE.

init with empty array add undefined to data.

Hi,

Initializing tinyqueue w/ empty array add undefined to data.

q = new require('tinyqueue')([])

{ data: [ undefined ],
length: 0,
compare: [Function: defaultCompare] }

Doesn't sort by properly

var comparator = function(a, b) {
  return a.cost - b.cost;
}

q = new TinyQueue([], comparator);
q.push({cost: 1120});
q.push({cost: 819});
q.push({cost: 592});
q.push({cost: 4930});

q.peek(); // Returns {cost: 4930}. Wrong.

README is inconsistent

Hello,

I noticed a bug in your README:

// add some items
queue.push(7);
queue.push(5);
queue.push(10);

// remove the top item
var top = queue.pop(); // returns 5

If it returns 5, its not the top. If its the top, documentation should say returns 7.

Does I miss something?

[Fork Information]: Commented Version Of This Module

I stumbled upon this module through these chain of events.

Being a noob both in programming at large and computer science in general, stumbling upon this module as the first implementation of heap data structure took me time to understand it. So I commented the code in the best way I could, so that noobs of the future could understand it a little easily, if they happen to stumble upon it the same (or different) way I did.

So I thought I would just open an issue to chain the information of the commented fork I made of this module.

That's it! 😅

Consider TypeScript typings

This would be great to have TypeScript typings on DefinitelyTyped.