堆

堆就是一棵完全二叉树

• B 站有我的详细讲解视频，欢迎关注一键三连！【面试官问一亿个数据怎么取前十榜单，这种 top k 问题你只会答先排序再取前十？今天一次性教会你堆排序与 top K 原理与实现学会后直接甩面试官脸上！（一）】

堆分为大顶堆跟小顶堆也叫大根堆和小根堆

• 大根堆是父节点均大于或等于子节点的一棵完全二叉树
• 小根堆是父节点均小于或等于子节点的一棵完全二叉树

那我们怎么创建一个堆呢？

• 假设我们当前存在一个如下图的数组：
• 可以看到我们的完全二叉树并不是一个合法的堆，因为图中最后一个子树不满足我们的堆的要求，那我我们只需要保证最后一棵子树满足要求即可，我们可以使用一个调整函数sift，来对我们的子树进行调整，使得其满足堆的条件。
• 我们调整整个堆采用农村包围城市的方案其调整思路如下（以大根堆为例）：
  • 我们假设调整的当前树的子树为合法的堆，那么我们只需要将当前堆顶元素放置到其合适的位置即可。
  • 因为我们假设了当前树的子树为一个合法的堆，那么我们可以从当前树的最后一个非叶子节点开始调整，因为这个子树是最后一个也是最小的一棵树。
  • 那么我们怎么找到最后一个非叶子节点呢？聪明的你一定已经发现了，完全二叉树父节点与子节点的关系：
    • 父节点找子节点：假设父节点索引为i，那么左孩子节点索引就是2 * i + 1，那么右孩子节点就是2 * i + 2。
    • 子节点找父节点：假设左孩子节点索引为i，那么父节点所谓就为 i >> 1，即当前索引整除以 2，左孩子我们没问题了，右孩子不满足这个条件怎么办？其实不难，我们可以通过找规律发现，假设右孩子索引为i，那么父节点索引就是(i - 1) >> 1，此时我们发现他的左孩子也满足这个条件，那么我们知道子节点索引找父节点公式就是(i - 1) >> 1。
    • 接下来我们需要进行交换位置，我们首先将子树的根节点缓存下来，假设该位置已经为空了，需要有一个孩子节点补上去，然后缓存下来的根节点放置到正确的位置即可。
    • 首先，我们找到两个子节点中值较大的子节点，接下来判断子节点中较大的值是否比缓存下来的值更大，如果更大，那么就交换两个的位置，也就是较大的到父节点去，此时我们的空位置就是刚才我们的较大的节点的位置，继续重复当前步骤，指到没有子节点比父节点更大或者没有子节点了就将缓存下来的值放置到空位置即可。
• 调整思路实现了之后我们开始构造堆，如上图，我们从最后一个非叶子节点开始调整，调整完毕之后索引前移，首先将红色框中根节点为 7 的子树开始调整，调整完毕之后样子为中间的图，此时我们调整的根节点前移一位，开始调整根节点为 8 的子树，此时这棵子树为合法的堆，我们跳出循环。然后调整的根节点进一步前移，开始调整根节点为 9 的图二，图二经过调整过后变为图三，此时我们的堆已经是一个合法的堆了。
• 调整函数如下：

function sift(arr: number[], low: number, high: number) {
  // 设空位置为i
  let i = low;
  // j代表i的子节点中较大的那个节点的索引位置
  let j = 2 * i + 1;
  const tmp = arr[i];
  // 当j索引没有越界
  while (j <= high) {
    // j+1也没有越界，判断右孩子是否比左孩子大，如果右孩子大那么就将右孩子索引赋值给j
    // 重述：j代表的是i的两个孩子中较大的那个节点的索引
    if (j + 1 <= high && arr[j + 1] > arr[j]) {
      j = j + 1;
    }
    // 当较大位置的值大于空位置的值
    if (arr[j] > tmp) {
      // 将更大的值赋值到空位置
      arr[i] = arr[j];
      //  空位置变成当前j的位置
      i = j;
      // j还是存的当前空位置的两个孩子中较大的那个，此时存的左孩子，
      // 下一次循环就会变成左右两个孩子中较大的那个位置索引
      j = 2 * i + 1;
    } else {
      // 如果较大的孩子的值小于或等于空位置的值那么就不需要进行调整直接退出
      break;
    }
  }
  // 调整结束后空位置的值就变成最初的位置的值
  arr[i] = tmp;
}
function sift(arr: number[], low: number, high: number) {
  // 设空位置为i
  let i = low;
  // j代表i的子节点中较大的那个节点的索引位置
  let j = 2 * i + 1;
  // 当j索引没有越界
  while (j <= high) {
    // j+1也没有越界，判断右孩子是否比左孩子大，如果右孩子大那么就将右孩子索引赋值给j
    // 重述：j代表的是i的两个孩子中较大的那个节点的索引
    if (j + 1 <= high && arr[j + 1] > arr[j]) {
      j = j + 1;
    }
    // 当较大位置的值大于空位置的值， 下次循环的i的值是本次循环j的值
    if (arr[j] > arr[i]) {
      // 交换空位置与较大的位置的值
      [arr[j], arr[i]] = [arr[i], arr[j]];
      //  空位置变成当前j的位置
      i = j;
      // j还是存的当前空位置的两个孩子中较大的那个，此时存的左孩子，
      // 下一次循环就会变成左右两个孩子中较大的那个位置索引
      j = 2 * i + 1;
    } else {
      // 如果较大的孩子的值小于或等于空位置的值那么就不需要进行调整直接退出
      break;
    }
  }
}

• 构造如下：

function heap(arr: number[]) {
  const high = arr.length - 1;
  // 构造堆  农村包围城市 -> 从最后一个非叶子节点开始挨个调整构造，一直到整个堆
  for (let i = (high - 1) >> 1; i >= 0; i--) {
    sift(arr, i, high);
  }
  return heap;
}

堆的应用

TopK 问题解决方案

• 什么是 TopK 问题？
  • TopK 表示从 n 个数据里找到前 K 大（小）的 K 条数据。
• 为什么不用先排序再进行前 K 个数据的切片呢？
  • 排序算法最快的是快排，时间复杂度是 O(n * logn),当我们的 n 特别大的时候，时间复杂度仍比较高。甚至我们的排序算法中的 slow 三人组（冒泡、选择、插入）性能也比先排序后切片要好，下面讲一下这三种排序为什么甚至性能比快排还要好。
  • 因为 slow 三人组，这三种排序方法，外层循环每进行一次遍历都可以找到最大（小）的一条数据，如果找前 K 条数据我们只需要循环 n * k 次即可，他们的时间复杂度为 O(n* k)，当 n 特别大 K 比较小时，总体时间复杂度优于上述先排序后切片。
• 堆为什么是作为解决 TopK 问题的最佳方案呢？（以从 n 个数中找前 K 大的数为例）
  • 首先，我们只是为了找 K 个数，那么我们没必要对全部数据进行排序，我们只需要使用堆维护一个大小为 K 的堆即可。
  • 假设我们找前 K 大的数，我们需要使用小根堆，因为小根堆的特点是堆顶元素小于堆中其他元素。
  • 接下来，我们先使用整个数据的前 K 条数据构建小根堆，然后遍历剩下的 n - k 条数据，当新来的数据大于堆顶元素时，我们将新来的元素与堆顶元素进行交换，然后进行一次向下调整，保证堆顶元素是最小的，也就是保证小根堆的合法性即可。
  • 遍历完全部数据后，我们堆中剩下的就是 n 条数据中前 K 大的数，只不过他们在堆中仍然是无序的，如果对顺序没有要求那么输出这个大小为 K 的堆即可；如果对顺序有要求那么我们可以使用堆排序中的挨个出数方法使其有序即可。
  • 可以发现我们使用堆进行处理，遍历整个 n 条数据是时间复杂度是 O(n)，我们的堆中有二分原理，堆的层数为 logK,复杂度为 O(logK)，整体的时间复杂度变为了 O(n * logK)，与上述两种解决方案相比使用堆来解决 TopK 问题是最优的解决方案。
• TopK 问题也可以使用BFPRT进行求解，这个算法在跟面试官吹牛的时候用就行，了解原理即可。

优先队列

• 什么是优先队列？
  • 优先队列是按照某个优先级顺序依次出队的数据结构。
• 堆怎么做优先队列？
  • 我们按照优先队列的某个优先级进行建堆，建完堆后每次只需要弹出堆顶即可，因为堆顶一定是优先级最高或者最低，有新的入队的时候我们进行一次向下调整即可满足优先队列的要求。

堆在框架中的应用

• 在 React 的任务调度器中使用了优先队列，优先队列就是用堆实现的，在 React 中用户的响应事件时最高优先级，使用优先队列可以用来优化用户的体验，减小用户界面的卡顿感，增强用户体验。