!TypeScript
!License: Apache-2.0

d-Heap Priority Queue (TypeScript) v2.5.0

A high-performance, generic d-ary heap priority queue with O(1) item lookup, supporting both min-heap and max-heap behavior.

Live Demo — Interactive visualization with Dijkstra's algorithm

Strengths

- Flexible behavior: min-heap or max-heap via comparator functions, and configurable arity d at construction time.
- Efficient operations on n items:
- O(1): access the highest-priority item (front(), peek()).
- O(log_d n): insert() and upward reheapification.
- O(d · log_d n): delete-top (pop()), with up to d children examined per level.
- O(1) item lookup: internal Map tracks positions by item key, enabling efficient priority updates.
- Practical API: insert, front, peek, pop, increasePriority, decreasePriority, updatePriority, isEmpty, len, contains.
- Unified API: Cross-language standardized methods matching C++, Rust, and Zig implementations.
- TypeScript-native: Full type safety, generics, and IDE support.
- Zero dependencies: No runtime dependencies.

Installation

``bash
npm install d-ary-heap
`

Quick Start

`typescript
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({
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

$3

`typescript
new PriorityQueue(options: PriorityQueueOptions)
`

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.

$3

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

$3

| 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) |

$3

| 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) |

$3

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

$3

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

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

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

// Max-heap by extracted key
const maxByCost = maxBy(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(t => t.priority),
minBy(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

$3

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

$3

`typescript
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();
`

$3

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) |

$3

Currently, instrumentation is implemented in TypeScript only. The table below shows the idiomatic zero-cost approach for each language, planned for v2.5.0:

| Language | Mechanism | Overhead When Disabled | Status |
|------------|----------------------------------|------------------------|--------|
| TypeScript | Optional hooks + instrumented comparator | Zero (JIT optimization) | ✅ Implemented |
| Go | Nil stats pointer | ~1 cycle (nil check) | Planned v2.5.0 |
| Rust | Generic over StatsCollector trait | Zero (monomorphization) | Planned v2.5.0 |
| C++ | Template policy class | Zero (inlining) | Planned v2.5.0 |
| Zig | Comptime bool parameter | Zero (branch elimination) | Planned v2.5.0 |

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

$3

| Operation | d=2 | d=4 | d=8 |
|-----------|-----|-----|-----|
| 100k inserts | ~21ms | ~13ms | ~11ms |
| 100k pops | ~187ms | ~136ms | ~140ms |
| Throughput (insert) | ~2.2M ops/sec | | |
| Throughput (pop+insert) | ~900k ops/sec | | |

$3

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.

$3

`bash

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

`bash

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).