简易优先队列(heap) js 版

这个优先队列使用数组存储。下面的代码是一个最大（不管是现实世界还是计算机的世界，什么是大什么是小，都是可以定义的）堆的实现。

基于堆的优先队列，出队，入队都是 logn 级别的时间复杂度。

提供 heapify 的实现。

2025-08-10 改动

优化了之前版本的实现，将 leftChildIndex/rightChildIndex/parentIndex 作为函数提取了出来，语义更明确；支持 comparator 的对比函数，实现最小或最大堆。

class MaxHeap {
  constructor(comparator = (a, b) => a - b) {
    this.heapList = [0]; // adding a dummy element at index 0
    this.heapSize = 0;
    this.comparator = comparator;
  }

  /**
   * 某个节点的左节点索引
   */
  _leftChildIndex(index) {
    return index * 2;
  }

  /**
   * 某个节点的右节点索引
   */
  _rightChildIndex(index) {
    return index * 2 + 1;
  }

  /**
   * 某个节点的父节点索引
   */
  _parentIndex(index) {
    return Math.floor(index / 2);
  }

  get size() {
    return this.heapSize;
  }

  getHeapList() {
    return this.heapList;
  }

  /**
   * 往堆中插入一个元素
   */
  insert(value) {
    if (!Array.isArray(value)) {
      throw new Error("Value must be an array, like [key, value]");
    }

    this.heapList.push(value);
    this.heapSize += 1;

    this._moveUp(this.heapSize);
  }

  _moveUp(position) {
    while (this._parentIndex(position) > 0) {
      const parent = this._parentIndex(position);

      if (
        this.comparator(this.heapList[position][1], this.heapList[parent][1]) >
        0
      ) {
        const temp = this.heapList[position];
        this.heapList[position] = this.heapList[parent];
        this.heapList[parent] = temp;

        position = parent;
      } else {
        break;
      }
    }
  }

  /**
   * 获取堆中最大的元素，但不删除它
   */
  findMax() {
    if (this.heapSize === 0) return null;

    return this.heapList[1];
  }

  /**
   * 取出堆中最大的元素
   */
  remove() {
    const maxValue = this.findMax();

    this.heapList[1] = this.heapList[this.heapSize];
    this.heapList.pop();
    this.heapSize -= 1;

    this._moveDown(1);

    return maxValue;
  }

  _moveDown(parentPosition) {
    while (this._leftChildIndex(parentPosition) <= this.heapSize) {
      const maxChildPosition = this._findMaxChild(parentPosition);

      if (
        this.comparator(
          this.heapList[maxChildPosition][1],
          this.heapList[parentPosition][1]
        ) > 0
      ) {
        const temp = this.heapList[maxChildPosition];

        this.heapList[maxChildPosition] = this.heapList[parentPosition];
        this.heapList[parentPosition] = temp;

        parentPosition = maxChildPosition;
      } else {
        break;
      }
    }
  }

  /**
   * 获取最大的子节点索引
   */
  _findMaxChild(position) {
    const leftChild = this._leftChildIndex(position);
    const rightChild = this._rightChildIndex(position);

    if (rightChild > this.heapSize) {
      return leftChild;
    }

    if (
      this.comparator(
        this.heapList[rightChild][1],
        this.heapList[leftChild][1]
      ) > 0
    ) {
      return rightChild;
    }

    return leftChild;
  }

  /**
   * 根据给定的数组构建最大堆 heapify
   */
  build(arrayList) {
    const len = arrayList.length;

    this.heapSize = len;
    this.heapList = [0, ...arrayList];

    let position = this._parentIndex(len);

    while (position > 0) {
      this._moveDown(position);
      position -= 1;
    }
  }
}

let heap = new MaxHeap();
// heap.insert(["a", 10]);
// heap.insert(["b", 20]);
// heap.insert(["c", 30]);
// heap.insert(["d", 40]);

heap.build([
  ["a", 10],
  ["b", 20],
  ["c", 30],
  ["d", 40],
]);

while (heap.size > 0) {
  console.log(heap.remove());
}