In a priority queue, you can...
- query or remove (poll) the smallest element quickly
- insert elements quickly
In practice, "quickly" often means in logarithmic time (O(log n)).
A heap can be used to implement a priority queue.
TypedPriorityQueue is an attempt to implement a performance-oriented priority queue in TypeScript. It can be several times faster than other similar libraries. It is ideal when performance matters.
License: Apache License 2.0
const x = new TypedPriorityQueue<number>();
x.add(1);
x.add(0);
x.add(5);
x.add(4);
x.add(3);
x.peek(); // should return 0, leaves x unchanged
x.size; // should return 5, leaves x unchanged
while(!x.isEmpty()) {
console.log(x.poll());
} // will print 0 1 3 4 5
x.trim(); // (optional) optimizes memory usage
You can also provide the constructor with a comparator function.
const x = new TypedPriorityQueue<number>(function(a,b) {return a > b});
x.add(1);
x.add(0);
x.add(5);
x.add(4);
x.add(3);
while(!x.isEmpty()) {
console.log(x.poll());
} // will print 5 4 3 1 0
If you are using node.js, you need to import the module:
import {TypedPriorityQueue} from 'typedpriorityqueue';
const b = new TypedPriorityQueue();// initially empty
b.add(1);// add the value "1"
The replaceTop
function allows you to add and poll in one integrated operation, which is useful fast top-k queries. See Top speed for top-k queries.
$ npm install typedpriorityqueue
The function calls "add" and "poll" have logarithmic complexity with respect to the size of the data structure (attribute size). Looking at the top value is a constant time operation.
Using node.js (npm), you can test the code as follows...
$ npm install mocha
$ npm test
It tends to fare well against the competition. In some tests, it can be five times faster than any other JavaScript implementation we could find.
$ node test.js
Platform: darwin 17.4.0 x64
Intel(R) Core(TM) i7-4770HQ CPU @ 2.20GHz
Node version 8.5.0, v8 version 6.0.287.53
Comparing against:
js-priority-queue: https://github.com/adamhooper/js-priority-queue 0.1.5
stablepriorityqueue: https://github.com/lemire/StablePriorityQueue.js 0.1.0
heap.js: https://github.com/qiao/heap.js 0.2.6
binaryheapx: https://github.com/xudafeng/BinaryHeap 0.1.1
priority_queue: https://github.com/agnat/js_priority_queue 0.1.3
js-heap: https://github.com/thauburger/js-heap 0.3.1
queue-priority: https://github.com/augustohp/Priority-Queue-NodeJS 1.0.0
priorityqueuejs: https://github.com/janogonzalez/priorityqueuejs 1.0.0
qheap: https://github.com/andrasq/node-qheap 1.4.0
yabh: https://github.com/jmdobry/yabh 1.2.0
starting dynamic queue/enqueue benchmark
TypedPriorityQueue x 27,029 ops/sec ±1.47% (83 runs sampled)
TypedPriorityQueue---replaceTop x 81,952 ops/sec ±2.18% (84 runs sampled)
sort x 6,835 ops/sec ±1.62% (85 runs sampled)
StablePriorityQueue x 2,414 ops/sec ±0.98% (85 runs sampled)
js-priority-queue x 4,096 ops/sec ±0.95% (88 runs sampled)
heap.js x 5,757 ops/sec ±0.80% (89 runs sampled)
binaryheapx x 3,186 ops/sec ±1.13% (85 runs sampled)
priority_queue x 2,555 ops/sec ±2.64% (82 runs sampled)
js-heap x 431 ops/sec ±1.24% (84 runs sampled)
queue-priority x 293 ops/sec ±4.03% (74 runs sampled)
priorityqueuejs x 6,191 ops/sec ±1.46% (86 runs sampled)
qheap x 23,370 ops/sec ±1.00% (86 runs sampled)
yabh x 3,653 ops/sec ±0.96% (88 runs sampled)
starting dynamic queue/enqueue benchmark
TypedPriorityQueue x 2,394 ops/sec ±1.59% (85 runs sampled)
TypedPriorityQueue---replaceTop x 9,449 ops/sec ±1.21% (86 runs sampled)
sort x 616 ops/sec ±0.93% (84 runs sampled)
StablePriorityQueue x 217 ops/sec ±1.84% (77 runs sampled)
js-priority-queue x 410 ops/sec ±1.04% (85 runs sampled)
heap.js x 461 ops/sec ±1.39% (81 runs sampled)
binaryheapx x 323 ops/sec ±1.25% (84 runs sampled)
priority_queue x 279 ops/sec ±1.16% (84 runs sampled)
js-heap x 41.28 ops/sec ±1.50% (53 runs sampled)
queue-priority x 31.40 ops/sec ±1.20% (55 runs sampled)
priorityqueuejs x 536 ops/sec ±1.13% (83 runs sampled)
qheap x 2,130 ops/sec ±1.15% (86 runs sampled)
yabh x 356 ops/sec ±1.63% (80 runs sampled)
Note that qheap
has been updated following the introduction of TypedPriorityQueue
, with a reference to TypedPriorityQueue
which might explains the fact that its performance is comparable to TypedPriorityQueue
.
A binary heap does not keep track of the insertion order.
If you like this library, you might also like