Dustin Boston

/**
 * @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:"]);
  });
});