js-pq

A high-performance generic Priority Queue implementation for JavaScript and TypeScript using a Binary Heap.

This project was developed for educational purposes to analyze and understand the state of priority queue implementations in JavaScript. I found the ecosystem mature and well-established.

Integration Considerations:

• If you require extreme performance and can work within its integer-only constraints, Heapify is the optimal choice.
• FlatQueue is an excellent option for managing objects where a custom comparator is not strictly required.
• FastPriorityQueue remains slightly faster for pure numeric data.
• TinyQueue offers a smaller codebase, which means smaller bundle size.
• heap-js is more feature-rich for advanced heap manipulations.

js-pq is for general-purpose applications that need a balance of performance and the flexibility of custom comparators.

Table of Contents

• Features
• Installation
• Usage
  • Basic Usage (Min-Heap)
  • Advanced Usage (Max-Heap with Objects)
  • O(n) Heapify
• API Documentation
• Performance Comparison
• License

Features

• 🚀 High Performance: Built with performance in mind, competitive with top-tier libraries like FastPriorityQueue.
• 🛠️ Generic Support: Handles any data type—numbers, strings, or complex objects—with a custom comparator.
• ⚡ Efficient Operations: O(log n) push/pop, O(1) peek, and O(n) heapify.
• 📦 Zero Dependencies: Lightweight and easy to integrate.
• TypeScript Support: Full type definitions included out of the box.

Installation

npm install js-pq

Usage

Basic Usage (Min-Heap)

By default, the queue acts as a Min-Heap for numbers.

import PriorityQueue from 'js-pq';

const pq = new PriorityQueue();
pq.push(10);
pq.push(5);
pq.push(20);

console.log(pq.peek()); // 5
console.log(pq.pop());  // 5
console.log(pq.size()); // 2

Advanced Usage (Max-Heap with Objects)

Use a custom comparator to manage complex objects. The comparator should return true if the first element has higher priority than the second.

const maxHeap = new PriorityQueue((a, b) => a.priority > b.priority);

maxHeap.push({ task: 'low', priority: 1 });
maxHeap.push({ task: 'high', priority: 10 });
maxHeap.push({ task: 'medium', priority: 5 });

console.log(maxHeap.pop()); // { task: 'high', priority: 10 }

O(n) Heapify

Construct a heap from an existing array efficiently.

const items = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
const pq = new PriorityQueue();
pq.heapify(items);

console.log(pq.pop()); // 1

API Documentation

new PriorityQueue(comparator?)

Creates a new priority queue.

• comparator: (Optional) A function (a, b) => boolean. Returns true if a should come before b.

.push(item)

Adds an item to the queue. Returns the new size.

• Time Complexity: O(log n)

.pop()

Removes and returns the item with the highest priority.

• Time Complexity: O(log n)

.peek()

Returns the item with the highest priority without removing it.

• Time Complexity: O(1)

.size()

Returns the number of items in the queue.

• Time Complexity: O(1)

.isEmpty()

Returns true if the queue is empty.

• Time Complexity: O(1)

.heapify(array)

Replaces the queue content with the provided array and builds a heap in place.

• Time Complexity: O(n)

Performance Comparison

Benchmarks performed on 1,000,000 random numbers (Total time for Push + Pop ops in ms):

Library	Push + Pop (1M)	Type	Best For
js-pq	114.81ms	Binary Heap	General use, high performance
FastPriorityQueue	112.08ms	Binary Heap	High performance, specific focus on numbers
TinyQueue	126.66ms	Binary Heap	Small code size, minimal API
heap-js	134.15ms	Binary Heap	Feature-rich API (extract, replace, etc.)
FlatQueue	129.66ms	Binary Heap	Optimized for complex object handling
Heapify	6.44ms	Integer Heap	Extreme performance for integers/indexes

License

MIT