@rbxts/heap

A TypeScript/roblox-ts binary heap (priority queue) implementation with support for both min-heap and max-heap configurations.

Features

• Min-heap and Max-heap: Static factory methods for creating min-heaps and max-heaps
• Custom comparators: Support for custom comparison functions
• Type-safe: Full TypeScript generics support for any value type
• Efficient operations: O(log n) push/pop, O(1) peek/isEmpty/size
• No external dependencies: Pure TypeScript implementation

Installation

npm install @rbxts/heap

Usage

Creating a Min-Heap

import { Heap } from "@rbxts/heap";

// Create a min-heap using the static factory
const minHeap = Heap.min((v: number) => v);

minHeap.push(5);
minHeap.push(3);
minHeap.push(7);

minHeap.peek(); // Returns 3
minHeap.pop();  // Returns 3
minHeap.pop();  // Returns 5

Creating a Max-Heap

import { Heap } from "@rbxts/heap";

// Create a max-heap using the static factory
const maxHeap = Heap.max((v: number) => v);

maxHeap.push(5);
maxHeap.push(3);
maxHeap.push(7);

maxHeap.peek(); // Returns 7
maxHeap.pop();  // Returns 7

Using Custom Comparators

import { Heap } from "@rbxts/heap";

// Create a heap with custom objects
interface Task {
    priority: number;
    name: string;
}

const taskHeap = new Heap<Task>((a, b) => a.priority < b.priority);

taskHeap.push({ priority: 5, name: "Low priority" });
taskHeap.push({ priority: 1, name: "High priority" });
taskHeap.push({ priority: 3, name: "Medium priority" });

const nextTask = taskHeap.pop();
// Returns { priority: 1, name: "High priority" }

Using Value Extractors

import { Heap } from "@rbxts/heap";

// Create a min-heap with a value extractor
const heap = Heap.min<{ value: number }>((v) => v.value);

heap.push({ value: 5 });
heap.push({ value: 3 });
heap.push({ value: 7 });

heap.peek()?.value; // Returns 3

API

Static Factory Methods

| Method | Description | |--------|-------------| | Heap.min<T>(extractValue: (v: T) => number): Heap<T> | Creates a min-heap that extracts a numeric value for comparison | | Heap.max<T>(extractValue: (v: T) => number): Heap<T> | Creates a max-heap that extracts a numeric value for comparison |

Constructor

new Heap<T>(compare: (a: T, b: T) => boolean)

• compare: A comparison function that returns true if a should come before b in the heap

Methods

| Method | Description | Time Complexity | |--------|-------------|------------------| | push(value: T): void | Adds a value to the heap | O(log n) | | pop(): T \| undefined | Removes and returns the root element | O(log n) | | peek(): T \| undefined | Returns the root element without removing it | O(1) | | isEmpty(): boolean | Returns true if the heap is empty | O(1) | | size(): number | Returns the number of elements in the heap | O(1) | | clear(): void | Removes all elements from the heap | O(n) |

Dependencies

This package has no external dependencies. It only uses built-in TypeScript/roblox-ts types and array methods.

License

MIT