luciopaiva/heapify

The fastest JavaScript priority queue out there. Zero dependencies.

🚑 🚴 🚌 🚕 🚗 🚚 🚛

A very fast JavaScript priority queue, implemented using a binary heap, which in turn is implemented using two underlying parallel typed arrays. No dependencies whatsoever; just plain, vanilla JS.

import {MinQueue} from "heapify";
// const {MinQueue} = require("heapify");  // alternatively, require() also works

const queue = new MinQueue();
queue.push(1, 10);
queue.push(2, 5);
queue.pop();  // 2
queue.peek();  // 1
queue.clear();
queue.pop();  // undefined

It's the fastest publicly available JavaScript library implementation of a priority queue. Here's a benchmark comparing Heapify to other popular libraries:

Operation	Closure	FlatQueue	TinyQueue	Heapify
build	201	n/a	n/a	18
push	222	66	75	24
pop	496	137	917	110
push/pop batch	279	83	280	89
push/pop interleaved	315	50	265	34
push/pop random	186	50	257	48

See the benchmark section for more details.

Heapify's design strives for reliability, with strong test coverage and focus on code readability. It should be easy to understand what the library is doing. The library is also very lean, with no dependencies and a small and concise source code.

Table of contents

• Features
• How to install
• How to import
• API
  • constructor
  • capacity
  • clear()
  • peek()
  • peekPriority()
  • pop()
  • push(key, priority)
  • size
• Benchmark
• Contributing

Features

Supported queue operations:

• push: O(log n)
• pop: O(log n) in the general case, O(1) if not preceded by a pop
• peek: O(1) in the general case, O(log n) if preceded by a pop
• peekPriority: O(1) in the general case, O(log n) if preceded by a pop
• creation with pre-existing list of priorities: O(n)

Other features:

• runs on browser and Node.js with ES5 and ES6 support
• tiny code base (under 200 LoC)
• no runtime dependencies
• supports several types of priorities and keys

How to install

npm i heapify

Or if you're a yarn person:

yarn add heapify

How to import

Node.js

You can import it in your Node.js project using TypeScript:

import {MinQueue} from "heapify";

Or directly via native ES6 module support, using the mjs ES6 module bundle:

import {MinQueue} from "heapify/heapify.mjs";

Or just require() it in your good old CommonJS project:

const {MinQueue} = require("heapify");

Browser

Heapify can be included via regular script tags, where Heapify will be exposed globally:

<script src="https://unpkg.com/heapify"></script>
<script>
  const {MinQueue} = Heapify;
</script>

The example above uses unpkg, but you can of course reference a local copy installed either manually or via npm/yarn.

For projects using native ES6 modules, make sure to import the mjs ES6 module bundle instead:

import {MinQueue} from "https://unpkg.com/heapify/heapify.mjs"

API

constructor(capacity = 64, keys = [], priorities = [], KeysBackingArrayType = Uint32Array, PrioritiesBackingArrayType = Uint32Array)

Creates a new priority queue. Parameters are:

• capacity: the size of the underlying typed arrays backing the heap;
• keys: an optional array of pre-existing keys. Provide [] to skip this field;
• priorities: an optional array of pre-existing priorities. Must match number of keys above. Provide [] to skip this field;
• KeysBackingArrayType: the array type to be used for keys;
• PrioritiesBackingArrayType: the array type to be used for priorities.

Example:

const queue1 = new MinQueue(32);
const queue2 = new MinQueue(16, [], [], Uint16Array, Uint32Array);

capacity

A read-only property that returns the maximum capacity of the queue. Example:

const queue = new MinQueue(32);
queue.capacity;  // 32

clear()

Effectively empties the queue. The heap capacity is not changed, nor its elements get erased in any way; it's just the variable that tracks the length that gets cleared to zero, so it's a very cheap operation.

Example:

const queue = new MinQueue();
queue.push(1, 10);
console.info(queue.size);  // 1
queue.clear();
console.info(queue.size);  // 0

peek()

Gets the key with the smallest priority, but does not remove it from the queue.

Example:

const queue = new MinQueue();
queue.push(1, 10);
queue.peek();  // 1

peekPriority()

Gets the priority of the key with the smallest priority, but does not remove the item from the queue.

Example:

const queue = new MinQueue();
queue.push(1, 10);
queue.peekPriority();  // 10

pop()

Removes the smallest priority item from the queue, returning its key. Returns undefined if the queue is empty.

Note that Heapify's heap implementation is not stable. If multiple keys have the same priority, there are no guarantees about the order in which they will be popped.

Example:

const queue = new MinQueue();
queue.push(1, 10);
queue.pop();  // 1

push(key, priority)

Adds a new item to the queue with a given key and priority. Will throw an error if the queue is already at its capacity.

Example:

const queue = new MinQueue();
queue.push(1, 10);
queue.size;  // 1
queue.peek();  // 1
queue.peekPriority();  // 10

size

A read-only property that returns the current size of the queue.

Example:

const queue = new MinQueue();
queue.size;  // 0
queue.push(1, 10);
queue.size;  // 1
queue.pop();
queue.size;  // 0

Benchmark

Here's a table comparing Heapify with other implementations (times are in milliseconds):

                             Closure     FastPQ  FlatQueue  TinyQueue    Heapify
build                            201         15          -          -         18
push                             222         47         66         75         24
pop                              496        143        137        917        110
push/pop batch                   279        128         83        280         89
push/pop interleaved             315         65         50        265         34
push/pop random                  186         45         50        257         48

Host machine: Node.js 13.8.0, 2.6 GHz 6-Core Intel Core i7, 32 GB 2400 MHz DDR4 RAM.

Operations:

• build - build queue from scratch by providing a collection of keys and priorities, all at once;
• push - insert a single element into the queue;
• pop - remove a single element from the queue;
• push/pop batch - performs batches of 1k pushes followed by 1k pops;
• push/pop interleaved - starting with a partially filled queue, this test inserts a random element and then immediately removes the lowest priority value from the queue;
• push/pop random - starting with a partially filled queue, this test runs either a push or a pop at random.

Each test performs 1 million operations and is repeated 5 times. The median value is used as the result.

Tested libraries:

• Google Closure library - a hugely popular library, but is the worst implementation with respect to performance;
• Fast Priority Queue - runs comparably fast, but doesn't support inserting keys as well, so its implementation significantly limits what the user is able to achieve with it;
• FlatQueue and TinyQueue - two very nice queue implementations by Vladimir Agafonkin. They don't support the build method and that's why they're missing this benchmark. FlatQueue performs considerably well for an implementation that is not based on typed arrays.

Contributing

You are welcome to contribute, but please take the time to read and follow these guidelines.

heapify's Issues

Add support for strings as key

priorityQueue.push("x,y", 10)
priorityQueue.push("a", 20)
console.log(priorityQueue.pop())    // 0
console.log(priorityQueue.peek())   // 0

The output should be

"x,y"
"a"

I want to use Dijkstra's algorithm on a 2D-array grid. Using indexes as keys and the number value at that position as weight.

Doesn't support duplicate priorities

The priority queue seems to give incorrect values when duplicate priorities are used.

When I try this:

const queue = new Heapify();
queue.push(1, 1);
console.log(queue.pop());
queue.push(2, 2);
console.log(queue.pop());
queue.push(3, 3);
queue.push(4, 5);
console.log(queue.pop());
queue.push(5, 4);
queue.push(6, 5);
console.log(queue.pop());
queue.push(7, 7);
console.log(queue.pop());
queue.push(8, 6);
console.log(queue.pop());

I would expect:
1 2 3 5 4 6 8 7

But I get:
1 2 3 5 4 8 6 7

So key 8 comes before key 6, even though the priority of key 6 is lower.

If this is intended behavior, I propose to add it to the documentation.

Get/Set Priority of Key

I don't know if this is outside the scope of this project, but while trying to implement Dijkstra's algorithm with this library I stumbled into this requirement. Basically I need to get and set the priority of a given key. Would love to know your thoughts on this @luciopaiva.

This is a min heap

From Upcoming features:, we can know that this is a min heap implementation. However, I think that it is quite confusing using highest priority in API section.

Adding TypeScript types

Hi @luciopaiva, nice package! I found this project through your post on reddit, which included some very nice details, thanks for taking the time to lay everything out so cleanly.

Has anybody brought up adding TypeScript types yet? I'd like to leverage this package in a strongly-typed codebase, which isn't possible to do right now without type-assertions galore.

There are three main approaches to providing types for this package:

1. use TypeScript as the implementation language

• Upsides:
  • type annotations come for free
  • leverage a fantastic static analysis tool (the type checker) and eliminate space for possible bugs to hide
  • types can never mis-represent behavior (or the TypeScript code wouldn't compile)
• Downsides:
  • invasive
  • takes time

2. publish types externally in DefinitelyTyped, so users can install the types with npm i @types/heapify

• Downsides:
  • not every version of heapify may be typed, only the versions with a corresponding @types/heapify version
  • takes additional time to manage externally, the DefinitelyTyped publishing process is human-gated and slow
  • users must install multiple packages to use this dependency in a strongly-typed environment

3. add a .d.ts file to this repo and specify it in package.json

• Upsides:
  • only one package to install for all users
  • every version of heapify can be published with types
• Downsides:
  • I've never created a harness to test that types aren't out of date/stale, although I'm sure it can be done
  • requires manually updating types
  • types could mis-represent behavior (since it's as loose a contract as documentation w/o being checked by a compiler)

The right path forward will be dependent on several factors, including

• your willingness to type this project internally (else 2 is the only option)
• your familiarity with TypeScript
• the amount of expected churn in the public API

Add a build heap method.

As we know, we could build a binary heap in O(n) time, are there any method to get this feature in this package?

Why faster than flatqueue?

Do you know why your implementation is faster than flatqueue? Is it the use of Uint32Array vs. JavaScript arrays?

Size and Capacity properties not on latest npm release

When installing this package via npm, the size and capacity properties recently added in commit 2e13f7d99c1b2f53c3e296ef42b3aa7bed088dfe aren't there.

Please update the npm package to match the readme. Thanks!

Documentation: What do peek() and peekPriority() return on empty heap

I could not find a description on what peek() and peekPriority() return when the heap is empty. pop() has a return type of number | undefined, and is documented to return undefined if the heap is emtpy, but peek() and peekPriority() both return just number.

Add support for updating priority of entry.

Since I'm trying to implement Dijkstra's algorithm, I want to be able to update the priority of an already existing entry in the queue.

Add support for Node.js require

Add support for being able to use require instead of import.

This is useful when working with Node.js and you for some reason can't use ES modules

remove arbitrary element [question]

I think the only way to remove entries from the Heapify queue is pop.

If so is the following approach optimal?

Could you please respond to or verify the inline remarks?

  const popEntry = () => {
    const priority = queue.peekPriority()
    const key = queue.pop()
    return { priority, key }
  }

  const poppedEntries = []

  // alternating peek/pop -> this loop is O(n) ?
  for (let entry = popEntry(); !removalPredicate(entry); entry = popEntry())
    poppedEntries.push(entry)

  // this loop is O(n lg n) ?
  //   - although ordering info is preserved
  //   - i.e. if poppedEntries were reverse iterated this loop would be doing push-min
  //   - it doesn't seem possible on the Heapify API to use this fact, but is that
  //       an API limitation or due to innate heap mechanics?
  for (let {key, priority} of poppedEntries)
    queue.push(key, priority)

Feature: peek() and pop() variants that return key and priority

I.e. something like this:

popItem(): [number, number] | undefined;
peekItem(): [number, number] | undefined;

Wrong behavior on v0.4.0

Hi,

The optimizations in v0.4.0 seem to have introduces erroneous behavior. My k-way merge algoritm, which produces nicely ordered results with v0.3.0, seems to be broken on v0.4.0.

Here's a snippet that reproduces the behavior for both the old and new versions:
https://codepen.io/tuner-the-typescripter/pen/mdMXQdE

Module breaks for large heap sizes

I tried adding 100,000 nodes to a heap and got some strange behaviour. The first few elements I pop have random values that I never added into the heap, but after a while, it starts working again.