JavaScript中如何实现堆？

堆是一种满足特定性质的完全二叉树数据结构，分为最大堆和最小堆两种常见类型，最大堆的父节点值大于等于子节点值，最小堆的父节点值小于等于子节点值。在JavaScript中没有内置的堆结构，需要开发者手动通过数组来模拟实现。

堆的基础特性

堆通常使用数组存储，对于数组中索引为i的节点，其左子节点索引为2*i+1，右子节点索引为2*i+2，父节点索引为Math.floor((i-1)/2)。这种存储方式可以高效完成节点之间的关系计算，不需要额外维护节点间的指针引用。

最大堆的实现

初始化堆结构

最大堆需要维护一个存储元素的数组，同时提供基础的交换元素、获取父节点索引等辅助方法。

class MaxHeap {
  constructor() {
    // 用数组存储堆的元素
    this.heap = [];
  }

  // 交换数组中两个索引位置的元素
  swap(i, j) {
    const temp = this.heap[i];
    this.heap[i] = this.heap[j];
    this.heap[j] = temp;
  }

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

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

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

插入元素

插入元素时先将新元素放到数组末尾，然后执行上浮操作，不断和父节点比较，若大于父节点则交换位置，直到满足最大堆的性质。

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

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

  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  // 插入元素方法
  insert(value) {
    // 将新元素放到数组末尾
    this.heap.push(value);
    // 执行上浮操作
    this.shiftUp(this.heap.length - 1);
  }

  // 上浮操作
  shiftUp(index) {
    if (index === 0) {
      return;
    }
    const parentIndex = this.getParentIndex(index);
    // 如果当前节点值大于父节点值，交换位置
    if (this.heap[index] > this.heap[parentIndex]) {
      this.swap(index, parentIndex);
      // 继续向上比较
      this.shiftUp(parentIndex);
    }
  }
}

删除堆顶元素

删除堆顶元素时，先将堆顶元素和数组最后一个元素交换，删除最后一个元素，再对新的堆顶元素执行下沉操作，不断和左右子节点中较大的值比较，若小于子节点则交换位置，直到满足最大堆性质。

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

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

  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  getLeftIndex(i) {
    return 2 * i + 1;
  }

  getRightIndex(i) {
    return 2 * i + 2;
  }

  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1);
  }

  shiftUp(index) {
    if (index === 0) {
      return;
    }
    const parentIndex = this.getParentIndex(index);
    if (this.heap[index] > this.heap[parentIndex]) {
      this.swap(index, parentIndex);
      this.shiftUp(parentIndex);
    }
  }

  // 删除并返回堆顶元素
  extractMax() {
    if (this.heap.length === 0) {
      return null;
    }
    const max = this.heap[0];
    // 将最后一个元素放到堆顶
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      // 执行下沉操作
      this.shiftDown(0);
    }
    return max;
  }

  // 下沉操作
  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);
    let largestIndex = index;
    // 找到当前节点和左右子节点中值最大的索引
    if (leftIndex < this.heap.length && this.heap[leftIndex] > this.heap[largestIndex]) {
      largestIndex = leftIndex;
    }
    if (rightIndex < this.heap.length && this.heap[rightIndex] > this.heap[largestIndex]) {
      largestIndex = rightIndex;
    }
    // 如果最大值不是当前节点，交换位置并继续下沉
    if (largestIndex !== index) {
      this.swap(index, largestIndex);
      this.shiftDown(largestIndex);
    }
  }
}

最小堆的实现

最小堆的实现逻辑和最大堆基本一致，仅比较规则相反，父节点值需要小于等于子节点值，插入时上浮、删除时下沉的比较条件都调整为小于判断即可。

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

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

  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  getLeftIndex(i) {
    return 2 * i + 1;
  }

  getRightIndex(i) {
    return 2 * i + 2;
  }

  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1);
  }

  shiftUp(index) {
    if (index === 0) {
      return;
    }
    const parentIndex = this.getParentIndex(index);
    // 最小堆上浮条件：当前节点值小于父节点值
    if (this.heap[index] < this.heap[parentIndex]) {
      this.swap(index, parentIndex);
      this.shiftUp(parentIndex);
    }
  }

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.shiftDown(0);
    }
    return min;
  }

  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);
    let smallestIndex = index;
    // 找到当前节点和左右子节点中值最小的索引
    if (leftIndex < this.heap.length && this.heap[leftIndex] < this.heap[smallestIndex]) {
      smallestIndex = leftIndex;
    }
    if (rightIndex < this.heap.length && this.heap[rightIndex] < this.heap[smallestIndex]) {
      smallestIndex = rightIndex;
    }
    if (smallestIndex !== index) {
      this.swap(index, smallestIndex);
      this.shiftDown(smallestIndex);
    }
  }
}

堆的应用场景

堆最常见的应用是实现优先队列，也可以用于堆排序，堆排序的时间复杂度为O(n log n)，属于原地排序算法。另外在需要获取前K大或前K小元素的场景中，使用堆也能将时间复杂度从O(n log n)优化到O(n log k)。

堆操作的时间复杂度

堆的插入和删除操作时间复杂度都是O(log n)，因为上浮和下沉操作最多遍历树的高度，而完全二叉树的高度为log n。获取堆顶元素的时间复杂度为O(1)，直接返回数组第一个元素即可。

JavaScript堆实现堆排序最大堆最小堆修改时间：2026-06-05 02:14:36