d-Heap Priority Queue (TypeScript) v2.6.0

Wikipedia-standard d-ary heap with configurable arity, O(1) item lookup, and zero-cost comparison-count instrumentation. Cross-language API parity with C++, Go, Rust, and Zig.

🎬 See it in action

Interactive demo →

Watch the heap tree update as items are inserted, popped, and re-prioritized. Toggle arity (d=2 / d=4 / d=8) to see how tree depth changes. Step through Dijkstra's algorithm on a weighted graph, or run race mode to compare all three arities side-by-side. Built with React Flow; runs in the browser, no install.

Why this crate?

If you already know you want a priority queue, here's what d-ary-heap gives you over js-priority-queue, priority-queue, and other npm alternatives:

• Configurable arity d (not just d=2). Pick d=4 for cache-friendlier inserts, d=8 for very insert-heavy workloads.
• O(1) item lookup + priority updates. increasePriority(item), decreasePriority(item), updatePriority(item) — the operations Dijkstra and A* actually need. Most npm priority-queue packages don't expose these.
• Zero-cost comparison-count instrumentation (in the library since v2.4.0; cross-language identical since v2.6.0). Opt-in instrumentComparator(...) + onBeforeOperation / onAfterOperation heap hooks; JIT-elided when not in use. See Instrumentation below.
• Cross-language API parity with Rust, Go, C++, and Zig — same method names, same complexity guarantees, byte-for-byte identical comparison counts on shared benchmarks (verified across 24 cells × 5 languages).
• Zero runtime dependencies. Full TypeScript types.
• Published numbers: see benchmarks/ for cross-language Dijkstra benchmarks (24 cells × 5 languages) and the methodology.

Installation

npm install d-ary-heap

Quick Start

import { PriorityQueue, minBy, maxBy } from 'd-ary-heap';

// Define your item type
interface Task {
  id: number;
  priority: number;
  name: string;
}

// Create a min-heap (lower priority value = higher importance)
const pq = new PriorityQueue<Task, number>({
  d: 4,                                    // 4-ary heap
  comparator: minBy(task => task.priority), // Min-heap by priority
  keyExtractor: task => task.id,           // Identity by id
});

// Insert items
pq.insert({ id: 1, priority: 10, name: 'Low priority task' });
pq.insert({ id: 2, priority: 1, name: 'High priority task' });
pq.insert({ id: 3, priority: 5, name: 'Medium priority task' });

// Get highest priority item (lowest priority value in min-heap)
console.log(pq.front()); // { id: 2, priority: 1, name: 'High priority task' }

// Update priority of existing item
pq.increasePriority({ id: 1, priority: 0, name: 'Now urgent!' });
console.log(pq.front()); // { id: 1, priority: 0, name: 'Now urgent!' }

// Remove items in priority order
while (!pq.isEmpty()) {
  console.log(pq.pop());
}

API Reference

Constructor

new PriorityQueue<T, K>(options: PriorityQueueOptions<T, K>)

Options:

• d: Number of children per node (arity). Default: 2. Must be >= 1.
• comparator: Function (a: T, b: T) => boolean returning true if a has higher priority.
• keyExtractor: Function (item: T) => K extracting the identity key from an item.
• initialCapacity: Optional hint for pre-allocation.

Static Factory Methods

| Method | Description | |--------|-------------| | PriorityQueue.withFirst(options, item) | Create queue with initial item |

Query Methods

| Method | Description | Time | |--------|-------------|------| | len() | Number of items | O(1) | | size | Property alias for len() | O(1) | | isEmpty() | Check if empty (primary method) | O(1) | | is_empty() | Alias for isEmpty() (cross-language compatibility) | O(1) | | d() | Get arity | O(1) | | contains(item) | Check if item exists (by key) | O(1) | | containsKey(key) | Check if key exists | O(1) | | getPosition(item) | Get item's index in heap | O(1) | | getPositionByKey(key) | Get index by key | O(1) | | front() | Get highest-priority item (throws if empty) | O(1) | | peek() | Get highest-priority item (returns undefined if empty) | O(1) |

Modification Methods

| Method | Description | Time | |--------|-------------|------| | insert(item) | Add new item | O(log_d n) | | pop() | Remove and return highest-priority item | O(d · log_d n) | | increasePriority(item) | Update item to higher priority (primary method) | O(log_d n) | | increase_priority(item) | Alias for increasePriority() (cross-language compatibility) | O(log_d n) | | increasePriorityByIndex(i) | Update by index (primary method) | O(log_d n) | | increase_priority_by_index(i) | Alias for increasePriorityByIndex() (cross-language compatibility) | O(log_d n) | | decreasePriorityByIndex(i) | Update by index (primary method) | O(d · log_d n) | | decrease_priority_by_index(i) | Alias for decreasePriorityByIndex() (cross-language compatibility) | O(d · log_d n) | | decreasePriority(item) | Update item to lower priority (primary method) | O(d · log_d n) | | decrease_priority(item) | Alias for decreasePriority() (cross-language compatibility) | O(d · log_d n) | | updatePriority(item) | Update item when direction unknown (primary method) | O((d+1) · log_d n) | | update_priority(item) | Alias for updatePriority() (cross-language compatibility) | O((d+1) · log_d n) | | clear(newD?) | Remove all items, optionally change arity | O(1) |

Utility Methods

| Method | Description | |--------|-------------| | toString() | String representation (primary method) | | to_string() | Alias for toString() (cross-language compatibility) | | toArray() | Copy of internal array | | [Symbol.iterator]() | Iterate over items in heap order |

Method Naming Convention

This TypeScript implementation follows camelCase as the primary naming convention (TypeScript/JavaScript standard), with snake_case aliases provided for cross-language compatibility:

• Primary methods: isEmpty(), increasePriority(), increasePriorityByIndex(), decreasePriority(), decreasePriorityByIndex(), updatePriority(), toString()
• Compatibility aliases: is_empty(), increase_priority(), increase_priority_by_index(), decrease_priority(), decrease_priority_by_index(), update_priority(), to_string()

Use the primary camelCase methods for TypeScript/JavaScript projects, and the snake_case aliases when porting code from C++/Rust implementations.

Comparator Helpers

import { minBy, maxBy, minNumber, maxNumber, reverse, chain } from 'd-ary-heap';

// Min-heap by extracted key
const minByCost = minBy<Item, number>(item => item.cost);

// Max-heap by extracted key
const maxByCost = maxBy<Item, number>(item => item.cost);

// For primitive numbers
const minHeap = minNumber;  // (a, b) => a < b
const maxHeap = maxNumber;  // (a, b) => a > b

// Reverse any comparator
const reversed = reverse(minByCost);

// Chain comparators (tiebreaker)
const byPriorityThenTime = chain(
  minBy<Task, number>(t => t.priority),
  minBy<Task, number>(t => t.timestamp)
);

Instrumentation (v2.4.0+)

The library provides opt-in instrumentation for counting comparisons during heap operations. This is useful for:

• Educational purposes: Understanding theoretical vs actual comparison costs
• Benchmarking: Measuring real comparison counts across different arities
• Visualization: Powering interactive demos that show heap behavior

Zero-Cost When Disabled

Instrumentation follows a zero-overhead design:

• No performance impact when not using instrumentation
• Existing code works unchanged
• Per-operation tracking distinguishes insert/pop/increasePriority/decreasePriority/updatePriority comparisons

Usage

import {
  PriorityQueue,
  minBy,
  instrumentComparator,
  theoreticalInsertComparisons,
  theoreticalPopComparisons
} from 'd-ary-heap';

// 1. Wrap your comparator with instrumentation
const comparator = instrumentComparator(minBy((v: Vertex) => v.distance));

// 2. Create priority queue with operation hooks
const pq = new PriorityQueue({
  d: 4,
  comparator,
  keyExtractor: (v) => v.id,
  onBeforeOperation: (op) => comparator.startOperation(op),
  onAfterOperation: () => comparator.endOperation(),
});

// 3. Use normally - comparisons are tracked automatically
pq.insert({ id: 'A', distance: 0 });
pq.insert({ id: 'B', distance: 5 });
pq.insert({ id: 'C', distance: 3 });
pq.pop();

// 4. Access statistics
console.log(comparator.stats);
// { insert: 3, pop: 2, decreasePriority: 0, increasePriority: 0, updatePriority: 0, total: 5 }

// 5. Compare with theoretical bounds
const n = 3;
const d = 4;
console.log('Theoretical insert (worst):', theoreticalInsertComparisons(n, d));
console.log('Theoretical pop (worst):', theoreticalPopComparisons(n, d));

// 6. Reset for next measurement
comparator.stats.reset();

Theoretical Complexity

For a d-ary heap with n elements:

| Operation | Comparisons (worst case) | |------------------|--------------------------------| | insert | floor(log_d(n)) | | pop | d × floor(log_d(n)) | | increasePriority | floor(log_d(n)) (moveUp only) | | decreasePriority | d × floor(log_d(n)) (moveDown only) | | updatePriority | (d+1) × floor(log_d(n)) (both) |

Cross-Language Consistency

Instrumentation is implemented in all five languages with byte-for-byte identical comparison counts (verified across 24 (graph, arity) cells; see benchmarks/README.md). Each language uses its idiomatic zero-cost mechanism:

| Language | Mechanism | Overhead When Disabled | |------------|-------------------------------------------------|------------------------| | TypeScript | Optional hooks + instrumented comparator | Zero (JIT optimization) | | Go | Nil stats pointer | ~1 cycle (nil check) | | Rust | Generic over StatsCollector trait | Zero (monomorphization + ZST layout) | | C++ | Template policy class + [[no_unique_address]] | Zero (inlining + ZST collapse) | | Zig | Comptime bool parameter on DHeapWithStats | Zero (branch elimination + void field type) |

Priority Update Semantics

This library uses importance-based semantics:

• increasePriority(): Make an item more important (moves toward heap root). Only moves up for O(log_d n) performance.
• decreasePriority(): Make an item less important (moves toward leaves). Only moves down for O(d · log_d n) performance.
• updatePriority(): Update when direction is unknown. Checks both directions for O((d+1) · log_d n) performance.

When to use each:

• Use increasePriority() when you know the item became more important
• Use decreasePriority() when you know the item became less important
• Use updatePriority() when you don't know which direction the priority changed

Heap Context:

• Min-heap: Lower priority values = higher importance
• Max-heap: Higher priority values = higher importance

Performance

Benchmarks

See benchmarks/ for the Phase 3 cross-language Dijkstra sweep (24 cells × 5 languages, K=2 warmup + 10 timed reps each, median + IQR reporting). On AMD Ryzen 9 5950X with Node v24.11.1, the TypeScript example runs huge_dense × d=8 (75 936 heap comparisons) at a median of 13.4 ms (~177 ns/cmp) — within 25% of Go's 11.0 ms / 145 ns/cmp on the same workload. The full methodology is in benchmarks/methodology.md.

Performance Tips

1. Choose arity wisely: d=4 is often optimal, balancing tree height vs comparison work per level.

2. Use inline comparators: (a, b) => a.cost < b.cost is faster than minBy(x => x.cost) in hot paths.

3. Pre-allocate: Use initialCapacity if you know the approximate size.

4. Simple key extractors: Keep keyExtractor simple—(item) => item.id is ideal.

5. Avoid unnecessary updates: Check if priority actually changed before calling update methods.

Running Benchmarks

# Full benchmark suite
npx tsx benchmarks/run-benchmarks.ts

# Compare with naive implementation
npx tsx benchmarks/compare-implementations.ts

What is a d-Heap?

A d-ary heap is a tree where:

• Each node has up to d children
• The root holds the highest priority
• Children are unordered
• Priorities decrease along any root-to-leaf path

Time complexities over n items:

• O(1): access top
• O(d · log_d n): delete-top
• O(log_d n): insert and upward update

Development

# Install dependencies
npm install

# Run tests
npm test

# Build
npm run build

# Type check
npm run typecheck

Reference

Section A.3, d-Heaps, pp. 773–778 of Ravindra Ahuja, Thomas Magnanti & James Orlin, Network Flows (Prentice Hall, 1993).

License

Apache License 2.0 — See LICENSE for details.