Various heap implementations for arbitrary values and with customizable ordering
npm install @thi.ng/heaps
!npm downloads
> [!NOTE]
> This is one of 214 standalone projects, maintained as part
> of the @thi.ng/umbrella monorepo
> and anti-framework.
>
> 🚀 Please help me to work full-time on these projects by sponsoring me on
> GitHub. Thank you! ❤️
- About
- Status
- Installation
- Dependencies
- API
- Heaps
- Priority queue
- Authors
- License
Various heap implementations for arbitrary values and with customizable ordering.
Type agnostic Heap and Priority Queue implementations with customizable
ordering and fanout / tree arity (in case of DHeap) and largely unified API:
- Binary heap (Heap)
- d-ary heap (DHeap)
- Pairing heap (PairingHeap)
- Priority queue (PriorityQueue)
STABLE - used in production
Search or submit any issues for this package
``bash`
yarn add @thi.ng/heaps
ESM import:
`ts`
import * as heaps from "@thi.ng/heaps";
Browser ESM import:
`html`
For Node.js REPL:
`js`
const heaps = await import("@thi.ng/heaps");
Package sizes (brotli'd, pre-treeshake): ESM: 2.00 KB
- @thi.ng/api
- @thi.ng/compare
- @thi.ng/equiv
Note: @thi.ng/api is in _most_ cases a type-only import (not used at runtime)
`ts
import { defDHeap } from "@thi.ng/heaps";
// with initial values, custom comparator and heap arity
const h = defDHeap
[5, 2, 10, 15, 18, 23, 22, -1],
{
// custom comparator
compare: (a, b) => b - a,
// branch size (DHeap only)
d: 4
}
);
h.pop();
// 23
h.pop();
// 22
// insert new value unless it's a new root
// else pop and return current root
h.pushPop(16)
// 18
h.push(24);
`
Even though all provided heap implementations support arbitrary values and
comparators and could be used as-is to implement a priority queue, since v1.3.0
this package also includes a dedicated
PriorityQueue
class, a thin veneer wrapper for a backing Heap and exposing a PQ-like API for
arbitrary values, with configurable value equality handling and priority
ordering:
- By default higher priority values mean higher priority
- Already queued items can be reprioritized or removed
- The queue head can be inspected via peek() and/or peekPriority()
without removing it from the queue
- Multiple items can be added at once via
- The queue is iterable (in priority order, according to given comparator)
`ts
import { defPriorityQueue } from "@thi.ng/heaps";
// use default config
const queue = defPriorityQueue();
// add items
queue.push(["alice", 5]);
queue.into([["bob", 3], ["charlie", 10], ["dora", 8]]);
// peek at top priority item
queue.peek()
// "charlie"
queue.peekPriority()
// 10
// reprioritize
queue.reprioritize("alice", 20)
// retrieve & remove top priority item
queue.pop()
// "alice"
`
If this project contributes to an academic publication, please cite it as:
`bibtex``
@misc{thing-heaps,
title = "@thi.ng/heaps",
author = "Karsten Schmidt",
note = "https://thi.ng/heaps",
year = 2017
}
© 2017 - 2026 Karsten Schmidt // Apache License 2.0