简易优先队列 js 版

这个优先队列使用数组存储。下面的代码是一个最大堆的实现。

class MaxHeap {
  constructor() {
    this.heapList = [0];
    this.heapSize = 0;
  }

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

    this.moveUp(this.heapSize);
  };

  moveUp = (position) => {
    while (Math.floor(position / 2) > 0) {
      const parent = Math.floor(position / 2);

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

      position = parent;
    }
  };

  remove = (value) => {
    const maxValue = this.heapList[1];
    this.heapList[1] = this.heapList[this.heapSize];
    this.heapList.pop();
    this.heapSize -= 1;

    this.moveDown(1);

    return maxValue;
  };

  moveDown = (parentPosition) => {
    while (parentPosition * 2 <= this.heapSize) {
      const maxChildPosition = this.findMaxChild(parentPosition);

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

      parentPosition = maxChildPosition;
    }
  };

  findMaxChild = (position) => {
    const leftChild = position * 2;
    const rightChild = position * 2 + 1;

    if (rightChild > this.heapSize) {
      return leftChild;
    } else {
      if (this.heapList[rightChild][1] > this.heapList[leftChild][1]) {
        return rightChild;
      } else {
        return leftChild;
      }
    }
  };

  build = (arrayList) => {
    const len = arrayList.length;

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

    let position = Math.floor(len / 2);

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

作者： 曾小乱

喜欢写点有意思的东西 查看曾小乱的所有文章