@himenon/priority-queue

A lightweight, high-performance priority queue implementation in TypeScript with flexible ordering (min-heap / max-heap) and built-in iterator support.
Designed for performance-critical applications and predictable memory usage, with behavior inspired by standard binary heap algorithms.

✨ Features

• ✅ Min-heap / Max-heap switching at runtime (setMinHeap, setMaxHeap)
• ✅ Custom priorities (number) per element
• ✅ Stable performance via binary heap (O(log n) enqueue/dequeue)
• ✅ Iterable: use in for...of, spread, etc.
• ✅ Bulk removal with drain() or sorted drainFast()
• ✅ Memory-efficient: optimized for minimal overhead
• ✅ Fully written in modern TypeScript, no dependencies

📦 Installation

pnpm i @himenon/priority-queue

🔧 Usage

import { PriorityQueue } from "@himenon/priority-queue";

const pq = new PriorityQueue<string>(); // Default: min-heap

pq.enqueue("task: low", 5);
pq.enqueue("task: high", 1);

console.log(pq.dequeue()); // => "task: high"

pq.setMaxHeap(); // switch dynamically
pq.enqueue("urgent", 10);
pq.enqueue("background", 1);

console.log([...pq]); // iterable

📈 Benchmark Results

The following charts compare this PriorityQueue implementation with yocto-queue, using statistical aggregates over 10 trials. Error bars represent the 25th to 75th percentile range.

📌 Notes

• Benchmarks were executed 10 times per heap size.
• All plots include mean values with p25–p75 error bars.
• Visualizations were generated via matplotlib in Docker.
• Raw CSV data and scripts can be found under benchmark/.

⏱️ Performance Considerations: PriorityQueue vs yocto-queue

This implementation of PriorityQueue adopts a binary heap internally in order to support prioritized ordering. While this introduces higher time complexity compared to plain FIFO queues like yocto-queue, it is a conscious trade-off that ensures ordering guarantees while maintaining low memory footprint.

📊 Comparison Table

| Operation | yocto-queue | PriorityQueue (this) | Complexity Increase | Reason | | ------------ | ----------------- | ---------------------- | ------------------- | ------------------------------------------ | | enqueue | O(1) | O(log n) | Yes 🔺 | Maintains heap order via bubbleUp | | dequeue | O(1) | O(log n) | Yes 🔺 | Requires heap reordering via bubbleDown | | peek | O(1) | O(1) | No ✅ | Both read front/root value | | drain | O(n) | O(n log n) | Yes 🔺 | Sequential dequeue() or heap sort | | Memory usage | Low (linked list) | Lower (flat array) | No ✅ | Binary heap stored as flat array (compact) |

🧠 Why the Priority Queue is Slower

Unlike yocto-queue, which is designed solely for FIFO operations and does not preserve any ordering beyond insertion time, PriorityQueue must always ensure that the highest or lowest priority item can be dequeued efficiently. This requires maintaining a partially ordered tree (heap), where insertion and removal involve comparisons and restructuring.

Thus, the increase in time complexity from O(1) to O(log n) is the necessary cost of enabling

LICENCE

@Himenon/priority-queue・MIT