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.

$3

- 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

``bash
npm install js-pq
`

Usage

$3

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

`javascript
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
`

$3

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

`javascript
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 }
`

$3

Construct a heap from an existing array efficiently.

`javascript
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

$3


Creates a new priority queue.
- comparator: (Optional) A function (a, b) => boolean. Returns true if a should come before b.

$3

Adds an item to the queue. Returns the new size.
- Time Complexity: O(log n)

$3

Removes and returns the item with the highest priority.
- Time Complexity: O(log n)

$3

Returns the item with the highest priority without removing it.
- Time Complexity: O(1)

$3

Returns the number of items in the queue.
- Time Complexity: O(1)

$3

Returns true if the queue is empty.
- Time Complexity: O(1)

$3

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