堆与优先队列

前言

想象一家急诊室。病人不断送来，但医生一次只能处理一个。怎么决定下一个处理谁？不是”先来先看”（那是队列），而是谁最紧急就看谁。

这就是优先队列（Priority Queue）的思想。它是队列的升级版：每次取出的不是最早进入的元素，而是优先级最高的元素。

堆（Heap）是实现优先队列最经典的数据结构。它能在 $O(\log n)$ 时间内插入一个元素、取出最大（或最小）元素。在贪心算法中，堆几乎是标配——每次选当前最优的操作，正是堆的拿手好戏。

问题的本质

为什么需要优先队列？

假设有 $N$ 个任务，每个任务有一个价值。你只有 $K$ 分钟，每个任务花 1 分钟。怎么选价值最大的 $K$ 个？

简单：把所有任务按价值排序，取前 $K$ 个。但如果任务在动态变化呢？比如你完成一个任务后，可能解锁新的任务。这时候排序就不够用了——你需要一个数据结构，每次快速取出当前最大值，同时能动态插入新元素。

这就是优先队列：

• 插入元素：$O(\log n)$
• 取出最大值：$O(\log n)$

堆的直觉：一场”锦标赛”

一棵完全二叉树，每个节点”打败”它的两个子节点（父节点 $\ge$ 子节点 = 大根堆）。根节点就是全局最大值——冠军。

取走冠军后，把最后一个叶子节点提上来当临时冠军，然后让它和子节点”比赛”：如果子节点更大，就交换（下沉）。这样冠军之位就确定了。插入新元素则相反：先放在最后，然后和父节点比较，更大就上浮。

理论 + 代码

二叉堆的结构

用数组存储完全二叉树。对于下标 $i$（从 1 开始）：

• 父节点：$i/2$
• 左子节点：$2i$
• 右子节点：$2i+1$

         [1] 最大值
        /   \
      [2]   [3]
     / \    / \
   [4] [5] [6] [7]

核心操作

上浮（heapify up）：新元素插入末尾，如果比父节点大就交换上去。

void up(int i) {
    while (i > 1 && heap[i] > heap[i/2]) { // ① 比父节点大就交换
        swap(heap[i], heap[i/2]);
        i /= 2;                              // ② 继续往上比较
    }
}

下沉（heapify down）：取走堆顶后，把最后一个元素放到堆顶，如果比子节点小就交换下去。

void down(int i) {
    while (2*i <= size) {        // ① 还有子节点
        int j = 2*i;             // ② 先选左子
        if (j+1 <= size && heap[j+1] > heap[j]) j++; // ③ 右子更大就选右子
        if (heap[i] >= heap[j]) break;  // ④ 已经满足堆性质
        swap(heap[i], heap[j]);
        i = j;                          // ⑤ 继续往下
    }
}

插入：放到末尾，上浮。取出最大值：把末尾元素移到堆顶，下沉。

每次上浮/下沉最多走 $\log n$ 层，所以两个操作都是 $O(\log n)$。

C++ priority_queue

实际竞赛中不需要手写堆，直接用 STL：

#include <queue>
using namespace std;

priority_queue<int> pq;           // ① 大根堆（默认）
priority_queue<int, vector<int>, greater<int>> pq2;  // ② 小根堆

pq.push(x);                       // ③ 插入 O(log n)
int t = pq.top();                 // ④ 查看堆顶 O(1)
pq.pop();                         // ⑤ 弹出堆顶 O(log n)
bool e = pq.empty();              // ⑥ 判空

注意：priority_queue 默认是大根堆。如果需要小根堆，用 greater<int> 作为比较器。

模拟走一遍

以大根堆 pq 为例，依次插入 3, 1, 4, 1, 5：

操作	堆（数组表示）	说明
push(3)	[3]	只有一个元素
push(1)	[3,1]	1 < 3，不上浮
push(4)	[4,1,3]	4 > 1，上浮交换；4 > 3，再上浮
push(1)	[4,1,3,1]	1 < 1，不上浮
push(5)	[5,4,3,1,1]	5 > 1，上浮；5 > 4，再上浮
pop()	[4,1,3,1]	弹出 5，末尾 1 补顶，下沉：1→4 交换
top()	4	当前最大值

例题

例题 1：TB A53 — Priority Queue

题目：实现一个销售系统，处理 $Q$ 个查询。查询有三种：

• 查询 1 1 x：添加一个价格 $x$ 的商品
• 查询 2 2：输出当前最便宜的商品价格
• 查询 3 3：卖出最便宜的商品（从系统中移除）

数据范围：$1 \le Q \le 10^5$

—— AtCoder Tessoku Book A53

分析：这是一个裸的小根堆。查询 1 插入，查询 2 查看堆顶，查询 3 弹出堆顶。

代码：

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int Q;
    scanf("%d", &Q);
    // ① 小根堆：最小的在堆顶
    priority_queue<int, vector<int>, greater<int>> pq;
    while (Q--) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int x;
            scanf("%d", &x);
            pq.push(x);           // ② 添加商品
        } else if (t == 2) {
            printf("%d\n", pq.top()); // ③ 查看最便宜的
        } else {
            pq.pop();             // ④ 卖出最便宜的
        }
    }
    return 0;
}

逐行解析：

• ① 用 greater<int> 创建小根堆。默认的 priority_queue<int> 是大根堆。
• ② 插入元素，$O(\log Q)$。
• ③ top() 返回堆顶（最小值），$O(1)$。
• ④ pop() 弹出堆顶，$O(\log Q)$。

---

例题 2：T90 048 — I will not drop out（★3）

题目：$N$ 道题，第 $i$ 题满分 $A_i$ 分，部分分 $B_i$ 分（$A_i/2 < B_i < A_i$）。每题花 1 分钟拿部分分，再花 1 分钟拿满分（每题最多花 2 分钟）。考试时间 $K$ 分钟，求最大总得分。

数据范围：$1 \le N \le 2 \times 10^5$，$1 \le K \le 2N$

—— AtCoder Typical 90 048

分析：把每道题拆成两个独立的”选项”：

• 选项 1：花 1 分钟，获得 $B_i$ 分
• 选项 2：花 1 分钟，额外获得 $A_i - B_i$ 分（前提是已经拿了 $B_i$）

但是选项 2 必须在选项 1 之后。不过注意：因为 $B_i > A_i/2$，所以 $A_i - B_i < B_i$，即选项 1 的收益总是大于选项 2。

所以正确的贪心策略：把所有选项放入大根堆，每次取最大的。因为选项 1 的值 $B_i > A_i - B_i$（选项 2），所以选项 1 自然先被取出。

但需要确保选项 2 在选项 1 之后被选。实际上，由于 $B_i > A_i - B_i$，如果堆里有选项 1，它一定会先于选项 2 被选出。所以直接把所有 $2N$ 个选项扔进堆，取前 $K$ 个。

代码：

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    priority_queue<long long> pq;  // ① 大根堆
    for (int i = 0; i < N; i++) {
        long long a, b;
        scanf("%lld%lld", &a, &b);
        pq.push(b);          // ② 选项1：花1分钟拿部分分 b
        pq.push(a - b);      // ③ 选项2：再花1分钟补满分（增量 a-b）
    }
    long long ans = 0;
    while (K-- && !pq.empty()) {
        ans += pq.top();     // ④ 每次取当前最大收益
        pq.pop();
    }
    printf("%lld\n", ans);
    return 0;
}

逐行解析：

• ②③ 把每题拆成两个选项。因为 $B_i > A_i - B_i$，选项 1 自然先被选出。
• ④ 贪心：每次选最大收益的操作，共选 $K$ 次。

验证：样例 $N=4, K=3$，$A=[4,9,15,8], B=[3,5,8,6]$。选项值：3,1,5,4,8,7,6,2。排序后：8,7,6,5,4,3,2,1。取前 3：8+7+6=21。✓

---

例题 3：动态中位数

场景：给定一个长度为 $N$ 的数组 $A$。对 $i=1,2,\ldots,N$，输出前 $i$ 个元素的中位数（奇数个时取中间值）。

方法：用两个堆——一个大根堆维护前半部分（较小的一半），一个小根堆维护后半部分（较大的一半）。

代码：

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    priority_queue<int> lo;                                     // ① 大根堆：存较小的一半
    priority_queue<int, vector<int>, greater<int>> hi;          // ② 小根堆：存较大的一半
    for (int i = 1; i <= N; i++) {
        int x;
        scanf("%d", &x);
        // ③ 保持 lo 的大小 = ceil(i/2)，即 lo.size() == hi.size() 或 lo.size() == hi.size()+1
        if (lo.empty() || x <= lo.top()) lo.push(x);
        else hi.push(x);
        // ④ 平衡两个堆的大小
        if ((int)lo.size() > (int)hi.size() + 1) {
            hi.push(lo.top()); lo.pop();
        }
        if ((int)hi.size() > (int)lo.size()) {
            lo.push(hi.top()); hi.pop();
        }
        // ⑤ 奇数个元素时输出中位数
        if (i % 2 == 1)
            printf("%d\n", lo.top());
    }
    return 0;
}

逐行解析：

• ①② 双堆法：lo 是大根堆存较小的一半（堆顶是较小部分的最大值），hi 是小根堆存较大的一半（堆顶是较大部分的最小值）。
• ③ 新元素根据和 lo.top() 的比较决定放入哪个堆。
• ④ 调整使得 lo.size() 始终等于或比 hi.size() 多 1。
• ⑤ 中位数就是 lo.top()。

---

例题 4：合并果子

场景：有 $N$ 堆果子，第 $i$ 堆有 $a_i$ 个。每次合并两堆，代价是两堆果子数之和。求把所有果子合并成一堆的最小总代价。

数据范围：$1 \le N \le 10^5$

分析：经典的哈夫曼编码问题。每次选最小的两堆合并——用小根堆。

代码：

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    for (int i = 0; i < N; i++) {
        long long a;
        scanf("%lld", &a);
        pq.push(a);          // ① 初始所有堆入队
    }
    long long ans = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();  // ② 取最小的
        long long b = pq.top(); pq.pop();  // ③ 取次小的
        ans += a + b;                       // ④ 合并代价
        pq.push(a + b);                    // ⑤ 新堆入队
    }
    printf("%lld\n", ans);
    return 0;
}

逐行解析：

• ① 初始把所有果子堆放入小根堆。
• ②③ 每次取出最小的两堆。因为小根堆堆顶始终是最小值，所以这两堆一定是当前最小的。
• ④ 合并代价 = 两堆大小之和，累加到答案。
• ⑤ 合并后的新堆放回小根堆，参与后续合并。
• 贪心正确性：类似于哈夫曼编码——每次合并最小的两堆，使得代价小的合并尽早发生，代价大的合并尽可能少发生。总时间 $O(N \log N)$。

参考文献

教材讲解 — 競技プログラミングの鉄則 第 8 章

• 8.3 B53 Taro’s Job（优先队列+贪心 解说）

系统练习 — 競技プログラミングの鉄則

• A53 Priority Queue（优先队列基础）【例题】

实战练习 — 競プロ典型 90 問

• 048 I will not drop out（★3，贪心+大根堆）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化