堆简介 🌳

堆是一种特殊的树状数据结构，每个节点都包含一个键值，且每个节点的键值都满足 大于等于/小于等于 其父节点的键值。

• 小根堆：每个节点的键值都大于等于其父节点的键值
• 大根堆：每个节点的键值都小于等于其父节点的键值

STL 中的 priority_queue 默认实现的是一个大根堆。

堆的核心操作 🛠️

• 插入元素：向堆中添加一个新元素
• 查询最值：获取堆中的最小/最大值
• 删除最值：移除堆中的最小/最大值
• 合并堆：将两个堆合并为一个
• 减小元素值：降低某个元素的键值（某些堆支持）

部分高级堆结构（如可并堆）还支持高效的合并操作，甚至支持可持久化（对历史版本进行查询或操作）。

堆的分类 📊

操作	配对堆	二叉堆	左偏树	二项堆	斐波那契堆
插入 (insert)	$O(1)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(1)$
查询最小值 (find-min)	$O(1)$	$O(1)$	$O(1)$	$O(1)$	$O(1)$
删除最小值 (delete-min)	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$
合并 (merge)	$O(1)$	$O(n)$	$O(\log n)$	$O(\log n)$	$O(1)$
减小元素值 (decrease-key)	$o(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(1)$
是否支持可持久化	❌	✅	✅	✅	❌

注：未特别说明时，堆 通常指二叉堆。

---

二叉堆 🔍

结构特性 🏗️

二叉堆是一种完全二叉树，每个节点存储一个元素（权值），并满足：

• 大根堆：父节点权值 $\geq$ 子节点权值
• 小根堆：父节点权值 $\leq$ 子节点权值

数组实现 📏

完全二叉树可通过数组高效实现，节点下标关系：

• 父节点 $i$ 的左子节点：$2i$
• 父节点 $i$ 的右子节点：$2i+1$
• 子节点 $i$ 的父节点：$\lfloor i/2 \rfloor$

本文介绍大根堆的实现。

核心操作 💡

插入操作 🌟

插入操作是指向二叉堆中插入一个元素，要保证插入后也是一棵完全二叉树。

• 最简单的方法就是，最下一层最右边的叶子之后插入。
• 如果最下一层已满，就新增一层。

插入之后可能会不满足堆性质？

向上调整 📚

如果这个结点的权值大于它父亲的权值，就交换，重复此过程直到不满足或者到根。

可以证明，插入之后向上调整后，没有其他结点会不满足堆性质。

向上调整的时间复杂度是 $O(\log n)$ 的。

具体实现

• 插入操作 $\text{push(x)}$

  • 将新元素置于末尾： $\text{a[++p] = x}; $
  • 调用 $\text{up(p)}$ 恢复堆性质。

伪代码

function up(i):
  while i > 1 and a[i] > a[i/2]:
    swap(a[i], a[i/2])
    i = i / 2
return

• 每次交换向上跳一层，最多 $\lfloor \log_2 p\rfloor$ 层；
• 故向上调整时间复杂度为 $\displaystyle O(\log n)$。

代码示例

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

获取最值 🔍

堆顶即最大值，位于数组下标 $1$：$\quad \texttt{return a[1]};$

时间复杂度：$\displaystyle O(1)$。

注意：堆不支持随机访问第 $k$ 大，仅能取最值。

删除操作 📝

删除操作指删除堆中最大的元素，即删除根结点。

但是如果直接删除，则变成了两个堆，难以处理。

所以不妨考虑插入操作的逆过程，设法将根结点移到最后一个结点，然后直接删掉。

通常采用的方法是，把根结点和最后一个结点直接交换。

• 将堆顶与最后一元素交换：$\text{swap}(a[1],\,a[p])$，并令堆大小 $p\leftarrow p-1$。

• 对新堆顶执行 向下调整 以恢复堆性质。

向下调整 📏

• 从根节点 $1$ 开始记为 $p$。
• 在该节点的左右儿子 $(2p,2p+1)$ 中找到一个最大的，与之交换。
• 重复该过程，直到底层。
• 向下调整的时间复杂度为 $O(\log n)$

伪代码

function down(i):
  while 2 * i <=  p:                  # 有至少一个子节点
    j = 2 * i                        # 左子节点
    if j + 1 <= p and a[j + 1] > a[j]:
      j = j + 1                      # 取两子中较大者
    if a[i] < a[j]:
      swap(a[i], a[j])
      i = j                        # 继续向下
    else:
      break
  end while

代码示例

void down(int i)
{
    while (i * 2 <= p)
    {
        int j = i * 2; // 获取左儿子编号
        if (j + 1 <= p && a[j + 1] > a[j]) j = j + 1; // 若右儿子存在且右儿子更大
        if (a[i] < a[j]) // 若小于较大的儿子就交换
        {
            swap(a[i], a[j]);
            i = j; // 令 i 等于 j 继续向下调整
        }
        else break; // 调整结束
    }
}
void pop() { a[1] = a[p--], down(1); }

增加某个点的权值 📏

很显然，直接修改后，向上调整一次即可，时间复杂度为 $O(\log n)$。

小根堆实现技巧 🎯

• 将原来判断 子节点 $>$ 父节点 改为 子节点 $<$ 父节点
• 取反 技巧
  • 插入时将元素取 负号：$\text{push(-x)}$
  • 查询或删除最小值时，返回或输出结果再去掉负号：$\text{-top()}$。

STL 的堆 📚

学习priority_queue

例题

[ABC234D] Prefix K-th Max

题意： 给定一个长度为 $n$ 的排列 $a_1, a_2, \dots, a_n$，对于每个前缀 $[a_1,\dots,a_i]$，动态维护并输出第 $k$ 大的元素。

思路： 维护一个小根堆

• 遍历 $i=1\dots n$：
  • 若堆大小 $<k$，则 $\text{push(a[i])}$
  • 否则若 $a_i > \text{top()}$，则先 $\text{pop()}$，再 $\text{push(a[i])}$；否则跳过。
• 每步输出当前堆顶：即前缀的第 $k$ 大元素。
• 时间复杂度：$O(n\log k)$

---

[ABC212D] Querying Multiset

题意： 给定一个空多重集合，需依次处理 $Q$ 次操作：

• 1 x：将整数 $x$ 插入集合；
• 2 x：将集合中所有元素统一加上 $x$；
• 3：删除并输出当前集合中的最小元素。

思路： 使用 $\textbf{小根堆}$ 维护集合中的 基准值。

• 维护一个全局偏移量 $\text{add}$，记录已累加的总和。
• 插入新元素 $x$ 时，存入堆中值 $x - \text{add}$，消除历史偏移。
• 删除（输出）最小值时，取堆顶 $y$，实际值为 $y + \text{add}$。
• 时间复杂度：$O(Q\log Q)$

---

动态中位数（对顶堆）

$n$ 次操作：维护一个序列，支持两种操作。

• 向序列中插入一个元素
• 若序列长度为奇数，输出当前序列的中位数

对于此类问题，我们可以使用 对顶堆 这一技巧予以解决。

对顶堆由一个大根堆 q1 与一个小根堆 q2 组成，小根堆维护大值，大根堆维护小值。

具体操作是这样的：

• 对于新输入的数字 $x$，若 $x$ 小于 q1.top()，则将 $x$ 插入 q1，否则插入 q2。
  • 小的数字进入大根堆，大的数字进入小跟队。

接下来需要做一些调整，其目的是为了保证大根堆的堆顶是当前序列中第 $k$ 大的数。

对于序列长度为奇数的情况，我们保证大根堆的元素个数比小根堆恰好多 $1$，如此使得大根堆的堆顶就是中位数。

调整策略：

• 当大根堆的元素个数小于小根堆。（小根堆元素多）
  • 此时把小根堆的堆顶加入大根堆。
• 当大根堆的元素个数多于小根堆的元素个数加 $1$。（大根堆元素多）
  • 此时把大根堆的堆顶加入小根堆。

如此使得 q1.size() - q2.size() <= 1 始终成立。

当序列长度为奇数时，可以确保大根堆堆顶是中位数。

#include <bits/stdc++.h>
using namespace std;
priority_queue<int> q1;
priority_queue<int, vector<int>, greater<int>> q2;
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (q1.empty() || x < q1.top()) q1.push(x);
        else q2.push(x);
        if (q1.size() < q2.size())
        {
            q1.push(q2.top());
            q2.pop();
        }
        if (q1.size() > q2.size() + 1)
        {
            q2.push(q1.top());
            q1.pop();
        }
        if (i & 1) cout << q1.top() << "\n";
    }
    return 0;
}

---

序列合并（多路归并）

题意： 给定两个长度为 $n$ 的序列 $a,b$，从 $n^2$ 组 $a_i + b_j$ 中选出前 $n$ 小的值。

思路:

将 $a, b$ 两序列排序后，所有 $a_i + b_j$ 的和可以排列成如下矩阵形式：

\[ \begin{cases} \underbrace{a_1 + b_1},\ a_1 + b_2,\ \cdots,\ a_1 + b_n \\ \underbrace{a_2 + b_1},\ a_2 + b_2,\ \cdots,\ a_2 + b_n \\ \vdots \\ \underbrace{a_n + b_1},\ a_n + b_2,\ \cdots,\ a_n + b_n \\ \end{cases} \]

• 每一行是以某个 $a_i$ 开头，按 $b_j$ 递增的和
• 每行第一个元素是该行最小值；
• 所有和中的最小值是 $a_1 + b_1$。

序列合并

从最小值 $a_1 + b_1$ 出发，我们每次取当前最小的和，然后生成该行的下一个候选值加入考虑。

\[ \begin{cases} \underbrace{a_1 + b_2},\ \cdots,\ a_1 + b_n \\ \underbrace{a_2 + b_1},\ a_2 + b_2,\ \cdots \\ \vdots \\ \underbrace{a_n + b_1},\ \cdots \\ \end{cases} \]

• 我们总是关注每一行的“当前头部元素”；
• 使用一个小根堆维护这些候选值，支持动态插入与删除最小值；
• 每次取出堆顶后，将对应行的下一个元素加入堆中。

实现细节：

• 使用小根堆 $\text{priority_queue}$，堆中存放三元组 $(\text{值},\ a\text{ 的下标},\ b\text{ 的下标})$

• 初始时，将所有 $a_i + b_1$ 连同其下标 $(i, 1)$ 一起入堆；

• 每次弹出堆顶 $(v,\ i,\ j)$，输出 $v$；
• 若 $j < n$，则将 $a_i + b_{j+1}$ 入堆，对应下标变为 $(i, j+1)$。

这种做法类似于 多路归并 的思路，时间复杂度为 $\mathcal{O}(n \log n)$

---

[NOIP2004 提高组] 合并果子

题意： 给定 $n$ 个数字 ${a_1, a_2, \dots, a_n}$，每次选择任意两个数字 $x,y$ 合并为 $x+y$，产生的代价为 $x+y$。

重复 $n-1$ 次合并后，问所有合并操作的总代价最小是多少？

思路： 贪心策略 + 小根堆

贪心原则：每次取出当前最小的两个数字合并，累加其和作为代价。

使用 小根堆（Min‐Heap） 动态维护剩余数字：

• 将所有 $a_i$ 插入小根堆；
• 重复 $n-1$ 次：
  • 弹出堆顶两元素 $x,y$；
  • 代价累加：$\mathrm{cost} \leftarrow \mathrm{cost} + (x+y)$；
  • 将合并结果 $x+y$ 再插入堆中。
• 时间复杂度：$O(n\log{n})$.

---

反悔贪心

若 每步取当前最优解 累积后能得到全局最优，则问题具备贪心性质。每一步只做局部最优选择，无需回溯。

反悔贪心

即便当前选择不完美，也先“接受”并继续前进，若后来发现不优再“反悔”撤销。

• 维护已选解的最优度（如最小/最大收益）；
• 发现更优选择时，用堆快速“弹出”旧选项、“插入”新选项；

例题：[USACO09OPEN] Work Scheduling G

题意： 有 $n$ 项任务，第 $i$ 项有截止时间 $d_i$ 和奖励 $p_i$。 每项任务耗时 $1$，问如何安排使得总奖励最大？

核心思路（一）：按截止时间贪心选取

• 将任务按截止时间 $d_i$ 升序排序；
• 依次扫描每个任务：
  • 若当前已安排任务数 $t < d_i$，则必做：将 $p_i$ 插入堆，$t$ 自增；
  • 否则（$t \ge d_i$），进入“反悔”阶段。
• 使用 小根堆 保存已选任务的奖励值，堆顶即当前最小奖励。

核心思路（二）：“反悔”替换最小奖励

• 当 $t \ge d_i$ 时:
  • 取出堆顶最小奖励 $p_{\min}$；
  • 若新任务 $p_i > p_{\min}$，则：
    • $\text{pop }p_{\min},\quad \text{push }p_i$
    • （用更大奖励替换），否则跳过当前任务。

最终结果

堆中所有任务即为最优安排，答案为堆中元素之和。

时间复杂度为：$O(n\log{n})$。