Home

Awesome

Heapify

codecov travis version

🚑 🚴 🚌 🚕 🚗 🚚 🚛

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:

OperationClosureFlatQueueTinyQueueHeapify
build201n/an/a18
push222667524
pop496137917110
push/pop batch2798328089
push/pop interleaved3155026534
push/pop random1865025748

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

Supported queue operations:

Other features:

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:

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:

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

Tested libraries:

Contributing

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