堆（Heap）数据结构

什么是堆？

堆（Heap）是一种特殊的完全二叉树，满足堆性质：

• 最大堆（Max Heap）：任意节点的值 ≥ 其子节点的值。
• 最小堆（Min Heap）：任意节点的值 ≤ 其子节点的值。

堆的常见操作

• insert(value)：插入新元素，时间复杂度 O(log n)
• extractMax() / extractMin()：取出并删除堆顶元素，时间复杂度 O(log n)
• peek()：查看堆顶元素，时间复杂度 O(1)
• buildHeap(array)：从数组构建堆，时间复杂度 O(n)

堆的应用场景

1. 任务调度：操作系统按优先级调度进程。
2. Top-K 问题：快速找出最大/最小的 K 个元素。
3. Dijkstra 算法：使用最小堆优化路径查找。
4. 堆排序（Heapsort）：基于堆的比较排序算法。

JavaScript 实现示例（最小堆）

class MinHeap {
  constructor() {
    this.heap = [];
  }

  getParentIndex(i) { return Math.floor((i - 1) / 2); }
  getLeftChildIndex(i) { return 2 * i + 1; }
  getRightChildIndex(i) { return 2 * i + 2; }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  peek() {
    return this.heap[0];
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) {
      this.swap(index, this.getParentIndex(index));
      index = this.getParentIndex(index);
    }
  }

  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return min;
  }

  heapifyDown() {
    let index = 0;
    while (this.getLeftChildIndex(index) < this.heap.length) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      if (this.getRightChildIndex(index) < this.heap.length &&
          this.heap[this.getRightChildIndex(index)] < this.heap[smallerChildIndex]) {
        smallerChildIndex = this.getRightChildIndex(index);
      }

      if (this.heap[index] < this.heap[smallerChildIndex]) break;
      this.swap(index, smallerChildIndex);
      index = smallerChildIndex;
    }
  }
}