支持减键的索引二叉最小堆

功能说明

该示例实现带索引的泛型二叉最小堆。普通堆在修改某个元素优先级时需要线性查找，本实现额外维护键到数组下标的映射，可以用 O(log n) 完成 decreaseKey，适合 Dijkstra 最短路、任务调度中的优先级提升以及事件时间推进等场景。比较器由调用方提供，因此可承载数字、对象或自定义优先级。

关键代码

节点同时保存键与值，positions 映射键到堆数组下标。push 先检查重复键，再追加并上浮；pop 取出根节点，删除其索引，把最后一个节点移到根位置并下沉；swap 在交换数组元素的同时更新两个键的位置。decreaseKey 只允许新值不大于旧值，否则抛 RangeError，然后原地更新并上浮，因为变小只可能向上调整。

使用注意

键必须在整个生命周期内唯一且非空，值变化时不会自动重排，必须调用 decreaseKey 或先删除再插入。不支持任意增加优先级；需要增大时应使用通用 update 或重新插入。比较器必须满足全序，否则堆结构可能失效。该实现不是线程安全的，也不能跨进程共享。pop 返回的是值而不是键，若需要键请改用 peekKey 或扩展返回值。

验证方式

按乱序插入若干数字并逐个弹出，断言输出单调不减；随机更新某个键为更小值，验证新的最小值顺序；测试重复键抛错、未知键减键抛错、减键传入更大值抛 RangeError；检查同键多次更新后位置映射仍正确；弹出到空后 peek 返回 undefined，且 size 归零。

代码示例

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);
  }
}