Package Exports
- @thi.ng/heaps
- @thi.ng/heaps/heap
This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@thi.ng/heaps) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.
Readme
This project is part of the @thi.ng/umbrella monorepo.
About
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
)
Status
STABLE - used in production
Search or submit any issues for this package
Installation
yarn add @thi.ng/heaps
// ES module
<script type="module" src="https://unpkg.com/@thi.ng/heaps?module" crossorigin></script>
// UMD
<script src="https://unpkg.com/@thi.ng/heaps/lib/index.umd.js" crossorigin></script>
Package sizes (gzipped, pre-treeshake): ESM: 1.97 KB / CJS: 2.04 KB / UMD: 2.12 KB
Dependencies
API
Heaps
import { defDHeap } from "@thi.ng/heaps";
// with initial values, custom comparator and heap arity
const h = defDHeap<number>(
[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);
Priority queue
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/orpeekPriority()
without removing it from the queue - Multiple items can be added at once via
into()
- The queue is iterable (in priority order, according to given comparator)
// 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"
Authors
Karsten Schmidt
If this project contributes to an academic publication, please cite it as:
@misc{thing-heaps,
title = "@thi.ng/heaps",
author = "Karsten Schmidt",
note = "https://thi.ng/heaps",
year = 2017
}
License
© 2017 - 2021 Karsten Schmidt // Apache Software License 2.0