Repository files navigation

🚑 🚴 🚌 🚕 🚗 🚚 🚛

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

import{MinQueue}from"heapify";// const {MinQueue} = require("heapify");  // alternatively, require() also worksconstqueue=newMinQueue();queue.push(1,10);queue.push(2,5);queue.pop();// 2queue.peek();// 1queue.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:

See thebenchmark 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.

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

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

npm i heapify

Or if you're a yarn person:

yarn add heapify

You canimport it in your Node.js project using TypeScript:

import{MinQueue}from"heapify";

Or directly vianative ES6 module support, using themjs ES6 module bundle:

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

Or justrequire() it in your good old CommonJS project:

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

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

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

The example above usesunpkg, 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 themjs ES6 module bundle instead:

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

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:

constqueue1=newMinQueue(32);constqueue2=newMinQueue(16,[],[],Uint16Array,Uint32Array);

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

constqueue=newMinQueue(32);queue.capacity;// 32

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:

constqueue=newMinQueue();queue.push(1,10);console.info(queue.size);// 1queue.clear();console.info(queue.size);// 0

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

Example:

constqueue=newMinQueue();queue.push(1,10);queue.peek();// 1

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

Example:

constqueue=newMinQueue();queue.push(1,10);queue.peekPriority();// 10

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

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

Example:

constqueue=newMinQueue();queue.push(1,10);queue.pop();// 1

Adds a new item to the queue with a givenkey andpriority. Will throw an error if the queue is already at its capacity.

Example:

constqueue=newMinQueue();queue.push(1,10);queue.size;// 1queue.peek();// 1queue.peekPriority();// 10

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

Example:

constqueue=newMinQueue();queue.size;// 0queue.push(1,10);queue.size;// 1queue.pop();queue.size;// 0

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

                             Closure     FastPQ  FlatQueue  TinyQueue    Heapifybuild                            201         15          -          -         18push                             222         47         66         75         24pop                              496        143        137        917        110push/pop batch                   279        128         83        280         89push/pop interleaved             315         65         50        265         34push/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 andTinyQueue - 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.

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