当前位置：首页 > JavaScript

js 堆实现

2026-02-01 03:49:52JavaScript

堆（Heap）简介

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

堆的实现关键点

存储结构：通常用数组表示堆，索引从0或1开始。父子节点关系可通过索引计算：
- 父节点索引：Math.floor((i - 1) / 2)（0-based）
- 左子节点索引：2 * i + 1
- 右子节点索引：2 * i + 2
核心操作：
- 插入（Insert）：将新元素添加到末尾，然后向上调整（heapifyUp）。
- 删除堆顶（Extract）：将堆顶与末尾交换，删除末尾，然后向下调整（heapifyDown）。
- 堆化（Heapify）：从最后一个非叶子节点开始向前调整。

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

  // 向上调整
  heapifyUp(index) {
    while (index > 0 && this.heap[index] < this.heap[this.getParentIndex(index)]) {
      const parentIndex = this.getParentIndex(index);
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

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

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

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

    if (smallest !== index) {
      this.swap(index, smallest);
      this.heapifyDown(smallest);
    }
  }

  // 插入元素
  insert(value) {
    this.heap.push(value);
    this.heapifyUp(this.heap.length - 1);
  }

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

  // 获取堆顶
  peek() {
    return this.heap[0] || null;
  }

  // 构建堆（从无序数组）
  buildHeap(arr) {
    this.heap = [...arr];
    for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
      this.heapifyDown(i);
    }
  }
}

使用示例

const heap = new MinHeap();
heap.insert(3);
heap.insert(1);
heap.insert(4);
console.log(heap.extractMin()); // 输出 1
console.log(heap.peek()); // 输出 3

// 构建堆示例
const heap2 = new MinHeap();
heap2.buildHeap([5, 3, 8, 1, 2]);
console.log(heap2.extractMin()); // 输出 1