Indexed Binary Min-Heap With Decrease-Key

export type Comparator<T> = (left: T, right: T) => number;

interface HeapNode<T> {
  key: string;
  value: T;
}

export class IndexedMinHeap<T> {
  private readonly nodes: HeapNode<T>[] = [];
  private readonly positions = new Map<string, number>();
  private readonly compare: Comparator<T>;

  constructor(compare: Comparator<T>) {
    if (typeof compare !== "function") throw new TypeError("compare must be a function");
    this.compare = compare;
  }

  get size(): number {
    return this.nodes.length;
  }

  has(key: string): boolean {
    if (typeof key !== "string" || key.length === 0) {
      throw new TypeError("key must be a non-empty string");
    }
    return this.positions.has(key);
  }

  peek(): T | undefined {
    return this.nodes[0]?.value;
  }

  get(key: string): T | undefined {
    const index = this.positions.get(key);
    return index === undefined ? undefined : this.nodes[index].value;
  }

  push(key: string, value: T): void {
    if (typeof key !== "string" || key.length === 0) {
      throw new TypeError("key must be a non-empty string");
    }
    if (this.positions.has(key)) throw new Error("duplicate key: " + key);
    const index = this.nodes.length;
    this.nodes.push({ key, value });
    this.positions.set(key, index);
    this.siftUp(index);
  }

  pop(): T | undefined {
    if (this.nodes.length === 0) return undefined;
    const root = this.nodes[0];
    const last = this.nodes.pop() as HeapNode<T>;
    this.positions.delete(root.key);
    if (this.nodes.length > 0) {
      this.nodes[0] = last;
      this.positions.set(last.key, 0);
      this.siftDown(0);
    }
    return root.value;
  }

  decreaseKey(key: string, value: T): void {
    const index = this.positions.get(key);
    if (index === undefined) throw new Error("unknown key: " + key);
    if (this.compare(value, this.nodes[index].value) > 0) {
      throw new RangeError("decreaseKey requires a smaller or equal value");
    }
    this.nodes[index].value = value;
    this.siftUp(index);
  }

  private siftUp(start: number): void {
    let index = start;
    while (index > 0) {
      const parent = (index - 1) >> 1;
      if (this.compare(this.nodes[index].value, this.nodes[parent].value) >= 0) break;
      this.swap(index, parent);
      index = parent;
    }
  }

  private siftDown(start: number): void {
    let index = start;
    while (true) {
      const left = index * 2 + 1;
      const right = left + 1;
      let smallest = index;
      if (left < this.nodes.length &&
        this.compare(this.nodes[left].value, this.nodes[smallest].value) < 0) {
        smallest = left;
      }
      if (right < this.nodes.length &&
        this.compare(this.nodes[right].value, this.nodes[smallest].value) < 0) {
        smallest = right;
      }
      if (smallest === index) break;
      this.swap(index, smallest);
      index = smallest;
    }
  }

  private swap(left: number, right: number): void {
    const leftNode = this.nodes[left];
    const rightNode = this.nodes[right];
    this.nodes[left] = rightNode;
    this.nodes[right] = leftNode;
    this.positions.set(rightNode.key, left);
    this.positions.set(leftNode.key, right);
  }
}