博客

class MinHeap {
  /**
   * 
   * @param {Array<Number>} data 
   */
  constructor() {
    this.data = [null];
  }

  /**
   * 返回堆大小
   * @returns Number
   */
  get size() {
    return this.data.length - 1;
  }

  /**
   * 返回队列中最小值
   */
  get min() {
    return this.data[1];
  }

  /**
   * 交换两个位置的值
   * @param {Number} i 
   * @param {Number} j 
   */
  _swap(i, j) {
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  }

  /**
   * 先把要插入的元素添加到堆底的最后，然后让其上浮到正确位置
   * @param {any} node 
   */
  insert(node) {
    this.data.push(node);
    this._swim(this.size);
    return this.data.slice(1);
  }

  /**
   * 先把堆顶元素 A 和堆底最后的元素 B 对调，然后删除 A，最后让 B 下沉到正确位置
   */
  delMin() {
    // 交换堆顶和堆底元素
    this._swap(1, this.size);
    // 保留最小值
    const min = this.data.pop();
    // 让堆顶元素下沉
    this._sink(1);
    return min;
  }

  /**
   * 上浮第 i 个元素，以维护最小堆性质
   * @param {Number} i 
   */
  _swim(i) {
    // 如果还没到堆顶并且 i 位置的值小于父元素，则交换
    while(i > 1 && this._less(i, this._getParentNodeIndex(i))) {
      this._swap(i, this._getParentNodeIndex(i));
      i = this._getParentNodeIndex(i);
    }
  }

  /**
   * 下沉第 i 个元素，以维护最小堆性质
   * @param {Number} i 
   */
  _sink(i) {
    while (this._getLeftNodeIndex(i) < this.size) {
      // 假设左子节点比较小
      let minIndex = this._getLeftNodeIndex(i);
      // 看一下右子节点是否存在，如果右子节点存在并且比左子节点小，便更新最小子节点的索引
      if (this._getRightNodeIndex(i) <= this.size && this._less(this._getRightNodeIndex(i), minIndex)) {
        minIndex = this._getRightNodeIndex(i);
      }
      // 如果该节点的值比两个子节点都小，就不用下沉了
      if (this._less(i, minIndex)) {
        break;
      }
      // 否则跟最小的交换
      this._swap(i, minIndex);
      // 更新i
      i = minIndex;
    }
  }

  /**
   * this.data[i] 是否比 this.data[j] 小
   * @param {Number} i 
   * @param {Number} j 
   * @returns Boolean
   */
  _less(i, j) {
    return this.data[i] < this.data[j];
  }

  /**
   * 获取 i 位置的父元素节点
   * @param {Number} i 
   */
  _getParentNode(i) {
    return this.data[this._getParentNodeIndex(i)];
  }

  /**
   * 获取 i 位置的父元素的索引
   * @param {Number} i 
   * @returns Number
   */
  _getParentNodeIndex(i) {
    /**
     * 已知父节点 p 的左子节点为 2p，右子节点为 2p + 1
     * 所以左子节点索引一定是偶数，右子节点索引一定是奇数
     */
    if (this._isLeftNode(i)) {
      return i / 2;
    } else {
      return (i - 1) / 2;
    }
  }

  /**
   * 获取 i 节点的左子节点
   * @param {Number} i 
   */
  _getLeftNode(i) {
    return this.data[this._getLeftNodeIndex(i)];
  }

  /**
   * 获取 i 节点的右子节点
   * @param {Number} i 
   */
  _getRightNode(i) {
    return this.data[this._getRightNodeIndex(i)];
  }

  /**
 * 获取 i 位置节点的左子节点索引
 * @param {Number} i 
 * @returns Number
 */
  _getLeftNodeIndex(i) {
    return 2 * i;
  }

  /**
   * 获取 i 位置节点的右子节点索引
   * @param {Number} i 
   * @returns Number
   */
  _getRightNodeIndex(i) {
    return 2 * i + 1;
  }

  /**
   * 判断 i 位置的节点是不是左节点
   * @param {Number} i 
   */
  _isLeftNode(i) {
    // 左节点索引一定是偶数
    return !this._isOdd(i);
  }

  /**
   * 判断 i 位置的节点是不是右节点
   * @param {Number} i 
   */
  _isRightNode(i) {
    // 左节点索引一定是偶数
    return this._isOdd(i);
  }

  /**
   * 判断一个数是否是奇数
   * @param {Number} num 
   * @returns Boolean
   */
  _isOdd(num) {
    return !!(num % 2);
  }
}