heaps

Note

This is one of 199 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

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

ESM import:

import * as heaps from "@thi.ng/heaps";

Browser ESM import:

<script type="module" src="https://esm.run/@thi.ng/heaps"></script>

JSDelivr documentation

For Node.js REPL:

const heaps = await import("@thi.ng/heaps");

Package sizes (brotli'd, pre-treeshake): ESM: 2.00 KB

Dependencies

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

API

Generated API docs

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/or peekPriority() 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)

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"

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 - 2024 Karsten Schmidt // Apache License 2.0