Reproduce

1. let queue_s = new FastPriorityQueue((a, b)=>{
   return a.priority <= b.priority;
   });
2. add 50 items in a queue, priority from 0~10
3. queue.forEach((value, index)=>{ if(value.priority == 3) value.priority = 0 }); // Change priority.
4. while (!queue_s.isEmpty()) {
   console.log(queue_s.poll());
   }
5. log like, wrong sort by priority

{ priority: 1, number: 22, serialNumber: 'Serial 22' }
{ priority: 1, number: 32, serialNumber: 'Serial 32' }
{ priority: 1, number: 38, serialNumber: 'Serial 38' }
{ priority: 0, number: 34, serialNumber: 'Serial 34' }
{ priority: 1, number: 42, serialNumber: 'Serial 42' }
{ priority: 0, number: 41, serialNumber: 'Serial 41' }
{ priority: 1, number: 25, serialNumber: 'Serial 25' }
{ priority: 2, number: 1, serialNumber: 'Serial 1' }
{ priority: 2, number: 45, serialNumber: 'Serial 45' }

But when I change
let queue_s = new FastPriorityQueue((a, b)=>{
return a.priority > b.priority;
});
All is OK.

The difference is change comparator from > to <=
Or should I copy values to another array and heapify again?

This is more of a suggestion / question for an enhancement than a bug or issue.

In short: expand poll and peek to values at indices other than 0.

In long: I am using the queue to keep track of properties on a set of elements. In my case, the set of elements can be split into two at some point, in which case I am creating a new set and update the old set (i.e., remove elements now being part of the new set). I would like to avoid having to re-heapify the elements on the old set so I expanded the poll function to accept an integer such that any value on the heap can be removed. Same addition for the peek.

The changes are minimal:

FastPriorityQueue.prototype.peek = function (i) {
    i = i | 0;
    if (this.size == 0 || i >= this.size) return undefined;
    return this.array[i];
};

FastPriorityQueue.prototype.poll = function (i) {
    i = i | 0;
    if (this.size == 0 || i >= this.size) return undefined;
    var ans = this.array[i];
    if (this.size > 1) {
        this.array[i] = this.array[--this.size];
        this._percolateDown(i);
    } else {
        this.size -= 1;
    }
    return ans;
};

(peek(i) is not expected to return the i-th element in terms of the priority but merely the i-th element on the array.)

I am wondering if this addition could be useful in general, hence, worth a pull request or if you want to keep things simple?

I've set up a fork and added a unit test in case you are interested: https://github.com/flekschas/FastPriorityQueue.js

This behavior is incorrect if the queue is empty.

If it's empty it ideally should return null, or some other predefined "no element" response.

Current behavior is confusing, wouldn't you agree?

A quick read of the source code and I reached the conclusion that minimist isn't required for this.

Can someone explain why it is included in package.json?

I run the following command

yarn add fastpriorityqueue

error [email protected]: The engine "node" is incompatible with this module. Expected version "~0.4".
error Found incompatible module
info Visit https://yarnpkg.com/en/docs/cli/add for documentation about this command.

I see that in https://github.com/lemire/FastPriorityQueue.js/blob/master/package.json#L26-L35 "queue-priority": "^1.0.0" is dependency but it is not really dependency it is used only in benchmark

Can you please remove all from dependencies and add it to benchmark folder only ?

Thanks for maintaining a wonderful library

I copied a lot of code from here and implemented a priority queue for a new memory cache library I'm making

Thanks for an awesome implementation that outshines its competitors.

Would it be possible to add an O(k) or O(klogk) algorithm for finding the k smallest elements of the queue?

It can be done in O(klogn) time right now by polling k times and then adding them all back.

An O(k) or O(klogk) algorithm is possible, however, as described here: https://stackoverflow.com/questions/47892037/finding-k-smallest-elements-in-a-min-heap-worst-case-complexity

Do you believe it would possible to implement? I'm likely gonna take a crack at it myself.

The latest publish to npm has a dependency on the npm package itself, which is causing our travis builds to fail. This is peculiar, because npm is not listed as a dependency anywhere in package.json or package-lock.json. Could you make sure that you don't have npm installed locally in the FastPriorityQueue.js folder and try publishing again, 0.6.1 I guess?

See here: https://www.npmjs.com/package/fastpriorityqueue. Previous versions did not have the npm dependency, and I don't think it should've been introduced in #16 because the dependencies in package.json did not change and it published correctly to here: https://www.npmjs.com/package/@exchangeunion/fastpriorityqueue.

Thanks.

I have a map of Queues and When I want to remove an element from a given queue the element itself is removed but the one below it got duplicated.

let mapOfQueues=new Map(); //a map of queues

let queue= new FastPriorityQueue(function(a, b) {
            return parseInt(a.priorite) < parseInt(b.priorite);
           });

mapOfQueues.set(key, queue);//add queue to map
let queueTarget = mapOfQueues.get(key);//retrieve queue from map 
var callback = function(val) {
return val.id==id;
}
let removedItem = queued.removeOne(callback);

elements are json object like
{
id: 130,
data: 'data',
priority: '20',
}

example

Queue is

{
  id: 130,
  data: 'data',
  priority: '20',
},
{
  id: 131,
  data: 'data',
  priority: '30',
},
{
  id: 132,
  data: 'data',
  priority: '40',
}

if element with id 131 is removed the queue becomes

{
  id: 130,
  data: 'data',
  priority: '20',
},
{
  id: 132,
  data: 'data',
  priority: '40',
},
{
  id: 132,
  data: 'data',
  priority: '40',
}

How can I iterate over queue? I have a scenario when I lost connection I must iterate over queue and remove some items (Not all)

Latest version on NPM is v0.2.4

https://www.npmjs.com/package/fastpriorityqueue

My benchmark on merging K number of sorted arrays yields slightly different result and qheap is faster. Let's maybe construct a set of meaningful tests in a separate repo so we can re-produce results and lock down versions of the libraries?

What library version did you use in your tests?

I noticed that you use different comparator functions, is there reason for it? Like for other libs you use a - b comparators and subtraction can be significantly slower than a < bthat you use for others. E.g. qheap supports this by default with comparBefore, but who knows maybe it's not a default for other libs. (e.g. js-priority-queue uses 3 way comparator and it seem to be the only option)

Also it seems https://github.com/andrasq/node-qheap has a reference to this very repo https://github.com/andrasq/node-qheap that shows that it's the fastest and claims it used to show it. What is going on? =)

When I updated comparators to be the same one, my local test also yielded similar result:

❯ node test.js
Platform: darwin 15.3.0 x64
Intel(R) Core(TM) i7-4850HQ CPU @ 2.30GHz
Node version 7.3.0, v8 version 5.4.500.45

Comparing against:
js-priority-queue: https://github.com/adamhooper/js-priority-queue
heap.js: https://github.com/qiao/heap.js
binaryheapx: https://github.com/xudafeng/BinaryHeap
priority_queue: https://github.com/agnat/js_priority_queue
js-heap: https://github.com/thauburger/js-heap
queue-priority: https://github.com/augustohp/Priority-Queue-NodeJS
priorityqueuejs: https://github.com/janogonzalez/priorityqueuejs
qheap: https://github.com/andrasq/node-qheap
yabh: https://github.com/jmdobry/yabh

starting dynamic queue/enqueue benchmark
FastPriorityQueue x 25,991 ops/sec ±1.90% (82 runs sampled)
js-priority-queue x 6,891 ops/sec ±1.50% (84 runs sampled)
heap.js x 2,428 ops/sec ±1.15% (86 runs sampled)
binaryheapx x 3,592 ops/sec ±1.04% (85 runs sampled)
priority_queue x 3,181 ops/sec ±1.37% (85 runs sampled)
js-heap x 236 ops/sec ±1.38% (78 runs sampled)
queue-priority x 366 ops/sec ±1.24% (84 runs sampled)
priorityqueuejs x 5,880 ops/sec ±0.93% (66 runs sampled)
qheap x 31,253 ops/sec ±1.23% (87 runs sampled)
yabh x 3,658 ops/sec ±1.14% (89 runs sampled)
Fastest is qheap

(btw another issue that test fails saying "pluck" doesn't exist, this is used to output last line)

Is it possible to use this lib to delay events?

We need a tool to schedule tasks for some time in the future. Is this library feet for such purposes?

Currently removeMany accepts a limit, which allows the iteration to stop based on number of items.

However, when we need to remove items that fall within a range, the no. of items to visit/remove are not known before hand. Request to add a shouldContinue kind of callback to the removeMany that allows the user to control if the removal is done or should proceed to next item.

This is useful to remove a continuous sequence of values in the queue.

For example, when input data contains duplicates, just doing poll once will not be sufficient. One has to remove all elements below the next higher value.

Or, when one wants to remove all values below certain limit x, one needs to keep removing items and stop once a value higher than x is encountered.

One can do it with repeat calls to poll, but since removeMany already exists, it would be great if a continuation control method can be added to it, that gives user more dynamic control on when to stop the iteration.

probably because this how priority queues are?

example that i put in these data:

{ name: 'a', no: 1}, { name: 'b', no: 1}, { name: 'c', no: 1}

what happens is after a call to poll() - it will pop "a" but the next in the queue would be "c" ?

Given a tree with the following priority values:

    1
  /   \
 1     2
/ \   / \
7 4   2 3

If I use traversal state or embedded data (rather than the priority itself) to determine whether I want to remove an object, then relying on removeMany for that operation may fail to check some items for removal, particularly when some items share the same priority.

Example, using traversal state:

var FastPriorityQueue = require("./FastPriorityQueue.js");

var saw2 = false;
var removed2 = false;

var fpq = new FastPriorityQueue();

[1,1,2,7,4,2,3].forEach(e => fpq.add(e));

fpq.removeMany(v => {
  console.log(v); // prints numbers in following order - 1,1,2,7,4,2,1,7,4,2
  if (v === 3) return true;
  if (removed2 || v !== 2) return false;
  if (!saw2) {
    saw2 = true;
    return false;
  }
  removed2 = true;
  return true;
});
fpq.trim();

fpq.array; // [ 1, 3, 1, 7, 4, 2 ]

The above case never checked for whether we should remove 3, so it remains in the priority queue.

The kSmallest function has a comment saying:

// return the k 'smallest' elements of the queue
// runs in O(k log k) time
// this is the equivalent of repeatedly calling poll, but
// it has a better computational complexity, which can be
// important for large data sets.

But it's not equivalent, because poll() removes the polled element and this function not. Example:

const FastPriorityQueue = require('fastpriorityqueue')

const q = new FastPriorityQueue()

q.add(1)
q.add(2)
q.add(3)

console.log(q.size)
// >> Outputs 3

q.kSmallest(2)

console.log(q.size)
// >> Outputs 3

for (let i = 0; i < 2; i++) {
  q.poll()
}

console.log(q.size)
// >> Outputs 1

Is this behavior expected? Either the comment or the documentation should be changed.

It's common to use array or object for rendering.

#19 is not published. Please publish it to npm.