二叉堆

定义

二叉堆是完全二叉树，且满足所有节点都≥（最大堆）或者≤（最小堆）其子节点的条件。

特点

• 所有节点都≥（最大堆）或者≤（最小堆）其子节点

存储方式

使用数组来存储二叉堆，从根节点出发，按根节点-左子节点-右子节点的顺序依次存入数组中，如下图所示

使用数组来存储二叉堆，有如下特点:

节点索引index，可以获取其子节点的索引

• 左子节点的索引是 2 * index + 1
• 右子节点的索引是 2 * index + 2

节点索引index，可以获取其父节点的索引

• 父节点的索引是 (index - 1) / 2

二叉堆的操作

二叉堆的自调整

上浮

如果节点不满足二叉堆的要求，则二叉树会自动调整自身结构，上浮操作是指节点从下到上调整位置

  // 上浮操作
  /** * * @param {*} arr : 二叉堆的物理底层存储数组 */
  // 这里使用了循环结构，也可以使用递归，每次递归都去比较子节点与父节点并交换双方的位置
  shiftUp(arr) {
    let childIndex = arr.length - 1;
    let parentIndex = Math.floor((childIndex - 1) / 2);
    const temp = arr[childIndex];
    // 开始上浮操作, 循环直到堆顶或者父节点不再大于子节点
    while(childIndex > 0 && arr[parentIndex] > temp) {
      // 子节点的值改写为父节点（即父节点下移）
      arr[childIndex] = arr[parentIndex];
      // 更新子节点的索引（即子节点跟父节点交换位置）
      childIndex = parentIndex;
      // 更新父节点的索引，下次循环继续比较父节点
      parentIndex = Math.floor((childIndex - 1) / 2);
    }
    // 循环结束后，将新节点的值赋予上浮操作的终点节点；
    arr[childIndex] = temp;
  }

下沉

  // 下沉操作
  /** * * @param {*} arr * @param {*} : 要下沉的节点 */
  shiftDown(arr, index) {
    let temp = arr[index];
    let parentIndex = index;
    let childIndex = 2 * parentIndex + 1;
    while (childIndex < arr.length) {
      // 首先要判断父节点与左右子节点的哪个进行交换, 要找到左右节点中更小的
      if (childIndex + 1 < arr.length && arr[childIndex + 1] < arr[childIndex]) {
        // 右节点更小，则让childIndex指向右节点
        childIndex ++;
      }
      if (temp < arr[childIndex]) {
        // 父节点比子节点更小，无需交换，直接退出循环
        break;
      }
      arr[parentIndex] = arr[childIndex];
      parentIndex = childIndex;
      childIndex = 2 * parentIndex + 1;
    }
    arr[parentIndex] = temp;
  }

插入节点

插入节点的操作可以看做是将新节点作为叶子节点插入，然后开始二叉堆自身调整的’上浮’操作。

  // 插入节点，时间复杂度为O(log(n)),其中n为二叉堆的容量（节点树）
  // 因为插入操作每次上浮一层，容量为n的二叉堆最大的可能上浮层数为log(n)
  /** * * @param {*} arr : 二叉堆的物理底层存储数组 * @param {*} node ：要插入的新节点, 节点的值即为node */
  insert(arr, node) {
    arr.push(node);
    this.shiftUp(arr);
  }

删除节点

删除节点，即将二叉堆的堆顶节点删除,具体操作是让堆的最后一个节点顶替堆顶节点，然后执行下沉操作

  // 删除节点, 从堆顶删除节点，时间复杂度同样为o(log(n))
  /** * * @param {*} arr : 二叉堆，这里是用数组来实现物理存储 */
  pop(arr) {
    let res = this.arr[0];
    this.arr[0] = this.arr.pop();
    this.shiftDown(this.arr, 0);
    return res;
  }

构建二叉堆

将一个无序的数组构建成一个二叉堆，包含了两种方式

依次将无序数组的元素插入二叉堆

constructor(array) {
    this.arr = [];
    for(let i = 0; i < array.length; i ++) {
      this.insert(this.arr, array[i]);
    }
  }

时间复杂度分析

这种方式下的时间复杂度为O(nlog(n)), 推导如下：

同一层的节点的最多交换次数是相同的，最后一层的叶子节点不需要执行交换，因为它的下面没有节点了。时间复杂度即为：O(sum(交换次数)) = O(每层节点数 * 该层节点的最多交换次数)。

n个节点的二叉堆层数为k = log(n)

S = 0 + 1 + 1 + 2 + 2 + 2 + 2 + ... + k + k + ... + k; (2个1，4个2，...., k-1个k)
求得S = k * 2^k - 2^(k-1) + 2;
即 S = nlog(n) - n/2 + 2;

将无序数组看做是不符合规则的二叉堆，从最后一个非叶子节点开始依次下沉操作

constructor(array) {
  this.arr = array;
  for(let i = Math.floor((this.arr.length - 1) / 2); i >=0; i --) {
    this.shiftDown(this.arr, i);
  }
}

时间复杂度分析

这种方式下的时间复杂度为O(n)，推导如下：

同一层的节点的最多交换次数是相同的，最后一层的叶子节点不需要执行交换，因为它的下面没有节点了。时间复杂度即为：O(sum(交换次数)) = O(每层节点数 * 该层节点的最多交换次数)。 n个节点的二叉堆层数为k = log(n), 层数d与d层的节点数dSum满足节点数dSum = 2 ^ (d - 1), 层数d的节点最多交换次数为log(k-d)，因此总的交换次数满足如下公式：

S = 2^0 * (k - 1) + 2^1 * (k -2) + ... + 2^(k-2) * [k- (k - 1)];
2S =                2^1 * (k - 1)+ ... + 2^(k-2) * [k - (k - 2)] + 2^(k-1) * [k - (k - 1)];
两式相减得到
S = 2^k - k - 1;
由于k = log(n)，因此
S = n - log(n) - 1;

所以时间复杂度为O(S) = O(n);

两种方式在于会不会改变传入的数组。

二叉堆的应用

• 高效快速找到最大值或最小值（时间复杂度O(1)）
• 找出第k个最大（小）元素（构建一个二叉堆，节点树为k（堆的容量为k））
• 找出前k个最大（小）元素（构建一个二叉堆，节点树为k（堆的容量为k））

找出第k个最大元素(见LeetCode 215)

• 构建一个最小堆，容量为k，将元素依次插入堆中
• 当堆的容量超过k时，删除堆顶，保持堆的容量不变
• 当所有元素都插入完毕时，堆顶元素即为第k个最大元素

找出前k个高频元素（见LeetCode 347）

优先队列

定义

• 最大优先队列：队列不再是先进先出，不管入队情况如何，值最大的元素先出队
• 最小优先队列：队列不再是先进先出，不管入队情况如何，值最小的元素先出队

实现

最大（小）优先队列可以使用最大（小）堆来实现。

// 最大优先队列,使用最大堆来实现
class PriorityQueue {
  /** * * @param {*} n : 队列长度 */
  constructor (n) {
    this.arr = [];
    this.size = n;
  }
  enQueue(element) {
    this.insert(this.arr, element);
    if (this.arr.length > this.size) {
      this.size ++;
    }
  }
  deQueue() {
    if (this.arr.length === 0) {
      throw new Error('no element!');
    }
    return this.pop();
  }
}