Nacho Pizza Marinade

    @thi.ng/heaps
    TypeScript icon, indicating that this package has built-in type declarations

    2.1.18 • Public • Published

    heaps

    npm version npm downloads Twitter Follow

    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:

    Status

    STABLE - used in production

    Search or submit any issues for this package

    Installation

    yarn add @thi.ng/heaps

    ES module import:

    <script type="module" src="https://cdn.skypack.dev/@thi.ng/heaps"></script>

    Skypack documentation

    For Node.js REPL:

    # with flag only for < v16
    node --experimental-repl-await
    
    > const heaps = await import("@thi.ng/heaps");
    

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

    Dependencies

    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)
    // 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 - 2022 Karsten Schmidt // Apache Software License 2.0

    Install

    npm i @thi.ng/heaps

    DownloadsWeekly Downloads

    624

    Version

    2.1.18

    License

    Apache-2.0

    Unpacked Size

    50 kB

    Total Files

    16

    Last publish

    Collaborators

    • thi.ng