/**
* @file Minimum Heap
* @author Dustin Boston
* @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
* Introduction to Algorithms. (2nd ed). The MIT Press.
* @see Computer Science and Artificial Intelligence Laboratory, MIT.
* {@link Heap Algorithms|https://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf}
* @see Chen, P. (n.d.). 6.5 Priority queues - CLRS Solutions.
* {@link CLRS 6.5-3|https://walkccc.me/CLRS/Chap06/6.5/#65-3}
*/
/**
* Represents a node in a min-heap with a priority key and an associated value.
* @template NodeValue - The type of the value associated with the node.
*/
export class Node<NodeValue> {
/**
* Creates an instance of a node with a given priority and an optional value.
* @param key - The priority of the node.
* @param value - An optional arbitrary value to associate with the priority.
*/
constructor(
public key: number,
public value: NodeValue | undefined = undefined,
) {}
/**
* Converts the node to a string representation.
* @returns The string representation of the node.
*/
toString(): string {
return `${this.key}:${String(this.value ?? "")}`;
}
}
/**
* A class representing a Min-Heap data structure.
* @template NodeValue - The type of the value stored in the heap nodes.
* @template NodeType - The type of the nodes, extending the Node class.
*/
export class MinHeap<NodeValue, NodeType extends Node<NodeValue>> {
/**
* Builds a min-heap from an array of nodes.
* @param array The array of nodes.
* @returns The constructed min-heap.
*/
static buildMinHeap<NodeValue, NodeType extends Node<NodeValue>>(
array: NodeType[],
): MinHeap<NodeValue, NodeType> {
const heap = new MinHeap<NodeValue, NodeType>(array, array.length);
for (let i = Math.floor(array.length / 2); i >= 0; i--) {
heap.minHeapify(i);
}
return heap;
}
/**
* Creates an instance of the MinHeap class.
* @param heap - An array of NodeType elements representing the heap.
* @param heapSize - The size of the heap. Defaults to 0.
*/
constructor(
public heap: NodeType[] = [],
public heapSize = 0,
) {}
/**
* Calculates the parent index of a node.
* @param index The index of the node.
* @returns The index of the parent node.
*/
parent(index: number): number {
return Math.floor((index - 1) / 2);
}
/**
* Calculates the left child index of a node.
* @param index The index of the node.
* @returns The index of the left child.
*/
leftChild(index: number): number {
return 2 * index + 1;
}
/**
* Calculates the right child index of a node.
* @param index The index of the node.
* @returns The index of the right child.
*/
rightChild(index: number): number {
return 2 * index + 2;
}
/**
* Returns the minimum element of the min-heap.
* @returns The minimum element in the heap.
* @throws If the heap is empty.
*/
heapMinimum(): NodeType {
if (this.heapSize === 0) {
throw new Error("Heap is empty");
}
return this.heap[0];
}
/**
* Extracts and returns the minimum element from the min-heap.
* @returns The minimum element that was extracted.
* @throws If the heap is empty (heap underflow).
*/
heapExtractMin(): NodeType {
if (this.heapSize <= 0) {
throw new Error("Heap underflow");
}
const min = this.heap[0];
this.heap[0] = this.heap[this.heapSize - 1];
this.heapSize--;
this.minHeapify(0);
return min;
}
/**
* Inserts a new key into the min-heap.
* @param node The node to insert.
*/
minHeapInsert(node: NodeType): void {
this.heapSize++;
const key = node.key;
node.key = Number.POSITIVE_INFINITY;
this.heap[this.heapSize - 1] = node;
this.heapDecreaseKey(this.heapSize - 1, key);
}
/**
* Decreases the key of an element at a given index in the min-heap.
* @param index The index of the element to decrease.
* @param newKey The new key value (must be less than or equal to the current key).
* @returns The new index of the element.
* @throws If the new key is greater than the current key.
*/
heapDecreaseKey(index: number, newKey: number): number {
if (!this.heap[index]) {
throw new Error("Invalid index for decrease key");
}
if (newKey > this.heap[index].key) {
throw new Error("New key is greater than current key");
}
this.heap[index].key = newKey;
while (
index > 0 &&
this.heap[this.parent(index)].key > this.heap[index].key
) {
this.exchange(index, this.parent(index));
index = this.parent(index);
}
return index;
}
/**
* Deletes an element at a given index from the min-heap.
* @param index The index of the element to delete.
* @returns The deleted element.
* @throws If the index is invalid.
*/
heapDelete(index: number): NodeType {
if (index < 0 || index >= this.heapSize) {
throw new Error("Invalid index for deletion");
}
this.heapDecreaseKey(index, Number.NEGATIVE_INFINITY);
const min = this.heapExtractMin();
this.heap.pop();
return min;
}
/**
* Maintains the min-heap property starting from a given index.
* @param index The index to start heapifying from.
*/
minHeapify(index: number): void {
const left = this.leftChild(index);
const right = this.rightChild(index);
let smallest = index;
if (left < this.heapSize && this.heap[left].key < this.heap[smallest].key) {
smallest = left;
}
if (
right < this.heapSize &&
this.heap[right].key < this.heap[smallest].key
) {
smallest = right;
}
if (smallest !== index) {
this.exchange(index, smallest);
this.minHeapify(smallest);
}
}
/**
* Exchanges two elements in the heap.
* @param indexA The index of the first element.
* @param indexB The index of the second element.
*/
exchange(indexA: number, indexB: number): void {
const temporary = this.heap[indexA];
this.heap[indexA] = this.heap[indexB];
this.heap[indexB] = temporary;
}
/**
* Prints the heap as a tree structure for easy debugging.
* @returns The tree structure representation of the heap.
*/
printHeapTree(): string {
return this.heap
.slice(0, this.heapSize)
.map((n) => n.toString())
.join(", ");
}
}
import {test, expect, describe, beforeEach} from "bun:test";
import {MinHeap, Node} from "./code.ts";
describe("Heap", () => {
let heap: MinHeap<never, Node<never>>;
beforeEach(() => {
heap = new MinHeap([], 0);
});
test("minHeapInsert and heapMinimum", () => {
heap.minHeapInsert(new Node(3));
heap.minHeapInsert(new Node(1));
heap.minHeapInsert(new Node(2));
expect(heap.heapMinimum().key).toBe(1);
});
test("heapExtractMin", () => {
heap.minHeapInsert(new Node(3));
heap.minHeapInsert(new Node(1));
heap.minHeapInsert(new Node(2));
expect(heap.heapExtractMin().key).toBe(1);
expect(heap.heapExtractMin().key).toBe(2);
expect(heap.heapExtractMin().key).toBe(3);
});
test("heapDecreaseKey", () => {
heap.minHeapInsert(new Node(3));
heap.minHeapInsert(new Node(1));
heap.minHeapInsert(new Node(2));
heap.heapDecreaseKey(2, 0);
expect(heap.heapMinimum().key).toBe(0);
});
test("heapDelete", () => {
heap.minHeapInsert(new Node(3));
heap.minHeapInsert(new Node(1));
heap.minHeapInsert(new Node(2));
heap.heapDelete(1); // 3
expect(heap.heapMinimum().key).toBe(1);
});
test("minHeapify", () => {
heap.heap = [new Node(3), new Node(1), new Node(2)];
heap.heapSize = 3;
heap.minHeapify(0);
expect(heap.heap.map((n) => n.toString())).toEqual(["1:", "3:", "2:"]);
});
});