二叉堆 | MarkCup

本篇将介绍二叉堆

二叉堆用于快速维护一系列数据中的最值

使用

STL 中的优先队列 priority_queue 就运用了二叉堆的数据结构

#include <queue>

priority_queue<int,vector<int>,greater<int>> q //类型声明，参数分别为<存放的类型,存放的容器,存放的比较方式>
//当 greater<int> 换成 less<int> 将存放小根堆,即由小到大
q.top() //访问顶部元素
q.empty() //检查容器适配器是否为空
q.size() //返回元素数量
q.push(1) //插入元素并对底层容器排序
q.pop() //移除顶部元素

结构

二叉堆由一个完全二叉树构成，后续讨论默认为大根堆，若需实现小根堆，只需修改不等号的方向即可
我们需要维护堆性质：每个父节点 不小于 其两个子节点。
由于这个性质，可以保证根节点即为最大值。

操作

插入

由于二叉堆为一个完全二叉树，所以我们只需要在 $n+1$ 的位置插入新的数据即可。
根节点为 $n/2$ ，兄弟节点为 $n \oplus 1$

接下来需要维护堆性质：从 $n+1$ 开始向上调整
反复比对新节点和他的父节点，如果新节点大于父节点，则和父节点交换，直至父节点大于新节点结束。

最坏情况下，需要从叶子节点一路交换至根节点，时间复杂度 $O(\log n)$

void up(int x) {
  while (x > 1 && h[x] > h[x / 2]) {
    swap(h[x], h[x / 2]);
    x /= 2;
  }
}

删除

想要删除最大值，不能直接删除根节点。这样会无法选择下方哪个子节点代替根节点。

所以我们使用序号最大的叶子节点 $n$ 代替根节点
接下来需要维护堆性质：从根节点向下调整
反复对比当前节点和他的两个子节点，如果两个子节点中最大的那个节点大于当前节点，则与其交换，直至当前节点大于等于他的两个子节点。

最坏情况下，需要从根节点一路交换至叶子节点，时间复杂度 $O(\log n)$

void down(int x) {
  while (x * 2 <= n) {
    t = x * 2;
    if (t + 1 <= n && h[t + 1] > h[t]) t++;
    if (h[t] <= h[x]) break;
    swap(h[x], h[t]);
    x = t;
  }
}

应用

对顶堆

当我们需要快速维护数据中第 $k$ 大的数据，可以使用对顶堆的方案
注：如果需要维护第 $k$ 小的数据，只需维护最大堆的数据数量即可

维护一个最小堆和一个最大堆，保证最小堆内的所有数据都大于等于最大堆内的数据，且最小堆中数据的数量不超过 $k$ 。

插入：
将新的数据插入至最小堆中，如果最小堆的数据数量超过了 $k$ ，那么将最小堆中的数据加入最大堆中。

删除：
删除第 $k$ 大的数据，只需将最小堆的堆顶删除，然后将最大堆的堆顶加入最小堆。

查询：
最小堆的堆顶，即为需求的第 $k$ 大的数据