js 堆实现

堆的概念

堆是一种特殊的完全二叉树，分为最大堆和最小堆。最大堆的每个父节点值大于或等于子节点值，最小堆的每个父节点值小于或等于子节点值。堆常用于优先队列、堆排序等场景。

堆的实现（基于数组）

堆通常用数组实现，利用完全二叉树的性质：

• 父节点索引为 i 时，左子节点索引为 2i + 1，右子节点为 2i + 2
• 子节点索引为 i 时，父节点索引为 Math.floor((i - 1) / 2)

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

  // 获取父节点索引
  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  // 获取左子节点索引
  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  // 获取右子节点索引
  getRightChildIndex(index) {
    return 2 * index + 2;
  }

  // 交换节点
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }

  // 插入节点
  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  // 删除堆顶节点
  extract() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return min;
  }

  // 向上调整
  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      this.swap(parentIndex, index);
      index = parentIndex;
    }
  }

  // 向下调整
  heapifyDown() {
    let index = 0;
    const length = this.heap.length;
    while (true) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);
      let smallest = index;

      if (leftChildIndex < length && this.heap[leftChildIndex] < this.heap[smallest]) {
        smallest = leftChildIndex;
      }

      if (rightChildIndex < length && this.heap[rightChildIndex] < this.heap[smallest]) {
        smallest = rightChildIndex;
      }

      if (smallest === index) break;
      this.swap(index, smallest);
      index = smallest;
    }
  }
}

堆的操作复杂度

• 插入操作：时间复杂度为 O(log n)，需要向上调整堆结构
• 删除操作：时间复杂度为 O(log n)，需要向下调整堆结构
• 获取堆顶元素：时间复杂度为 O(1)

堆的应用示例

const heap = new MinHeap();
heap.insert(3);
heap.insert(1);
heap.insert(6);
heap.insert(5);
console.log(heap.extract()); // 输出 1
console.log(heap.extract()); // 输出 3

最大堆实现

将最小堆的比较逻辑反转即可实现最大堆：

class MaxHeap extends MinHeap {
  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[parentIndex] >= this.heap[index]) break;
      this.swap(parentIndex, index);
      index = parentIndex;
    }
  }

  heapifyDown() {
    let index = 0;
    const length = this.heap.length;
    while (true) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);
      let largest = index;

      if (leftChildIndex < length && this.heap[leftChildIndex] > this.heap[largest]) {
        largest = leftChildIndex;
      }

      if (rightChildIndex < length && this.heap[rightChildIndex] > this.heap[largest]) {
        largest = rightChildIndex;
      }

      if (largest === index) break;
      this.swap(index, largest);
      index = largest;
    }
  }
}