Socket
Socket
Sign inDemoInstall

@thi.ng/heaps

Package Overview
Dependencies
3
Maintainers
1
Versions
166
Alerts
File Explorer

Advanced tools

Install Socket

Detect and block malicious and high-risk dependencies

Install

@thi.ng/heaps

Various heap implementations for arbitrary values and with customizable ordering


Version published
Maintainers
1
Weekly downloads
548
decreased by-45.58%

Weekly downloads

Readme

Source

@thi.ng/heaps

npm version npm downloads Mastodon Follow

[!NOTE] This is one of 190 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

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:

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

Package sizes (brotli'd, pre-treeshake): ESM: 2.01 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)
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

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

Keywords

FAQs

Last updated on 27 Mar 2024

Did you know?

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc