堆数据结构

最大堆

class maxHeap {
  constructor() {
    this._heap = [];
  }
  get peek() {
    return this._heap[0];
  }
  get size() {
    return this._heap.length;
  }

  up(index) {
    let pIndex = this._getPindex(index);
    // 最大堆：大于父节点上移
    if (this._heap[index] > this._heap[pIndex]) {
      this.swap(index, pIndex);
      this.up(pIndex);
    }
  }
  down(index) {
    // 下移的时候需要判断子节点哪一个大 ，和大的对比然后调换
    let lIndex = this._getLeft(index);
    let rIndex = this._getRight(index);
    let maxIndex = this._heap[lIndex] > this._heap[rIndex] ? lIndex : rIndex;

    if (this._heap[index] < this._heap[maxIndex]) {
      this.swap(index, maxIndex);
      this.down(maxIndex);
    }
  }

  insert(item) {
    this._heap.push(item);
    this.up(this.size - 1);
  }
  pop() {
    if (!this.size) {
      return;
    }
    if (this.size === 1) {
      this._heap.pop();
    } else {
      this._heap[0] = this._heap.pop();
      this.down(0);
    }
  }
  swap(i, j) {
    [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
  }

  _getLeft(index) {
    return 2 * index + 1;
  }

  _getRight(index) {
    return 2 * index + 2;
  }

  _getPindex(index) {
    return (index - 1) >> 1;
  }
}

最小堆

class minHeap {
  constructor() {
    this._heap = [];
  }
  get peek() {
    return this._heap[0];
  }
  get size() {
    return this._heap.length;
  }

  up(index) {
    let pIndex = this._getPindex(index);
    // 最小堆：小于父节点上移
    if (this._heap[index] < this._heap[pIndex]) {
      this.swap(index, pIndex);
      this.up(pIndex);
    }
  }
  down(index) {
    // 下移的时候需要判断子节点哪一个更小 ，和大的对比然后调换
    let lIndex = this._getLeft(index);
    let rIndex = this._getRight(index);
    let minIndex = this._heap[lIndex] < this._heap[rIndex] ? lIndex : rIndex;

    if (this._heap[index] > this._heap[minIndex]) {
      this.swap(index, minIndex);
      this.down(minIndex);
    }
  }

  insert(item) {
    this._heap.push(item);
    this.up(this.size - 1);
  }
  pop() {
    if (!this.size) {
      return;
    }
    if (this.size === 1) {
      this._heap.pop();
    } else {
      this._heap[0] = this._heap.pop();
      this.down(0);
    }
  }
  swap(i, j) {
    [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
  }

  _getLeft(index) {
    return 2 * index + 1;
  }

  _getRight(index) {
    return 2 * index + 2;
  }

  _getPindex(index) {
    return (index - 1) >> 1;
  }
}