npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

typedpriorityqueue

v1.0.1

Published

Fast heap-based priority queue in TypeScript

Downloads

3

Readme

TypedPriorityQueue : a fast heap-based priority queue in TypeScript

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

Usage

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

  $ npm install typedpriorityqueue

Computational complexity

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.

Testing

Using node.js (npm), you can test the code as follows...

  $ npm install mocha
  $ npm test

Is it faster?

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.

Insertion order

A binary heap does not keep track of the insertion order.

You might also like...

If you like this library, you might also like

  • https://github.com/lemire/FastBitSet.js
  • https://github.com/lemire/StablePriorityQueue.js
  • https://github.com/lemire/FastIntegerCompression.js