---
title: "堆与优先队列"
description: "大根堆与小根堆、建堆与调整，以及 priority_queue 的用法。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 堆与优先队列

排序之后取最大值很快，但一边插入新元素一边反复取最大值，排序就不够用了。堆就是为这种场景设计的：插入和取最值都是 $O(\log n)$，而且取最值只要 $O(1)$。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

| 考试 | 大纲要求 | 本章位置 |
| --- | --- | --- |
| CSP-J/S 提高级 | 2.3.1 优先队列；2.3.3 二叉堆 | 全章 |
| GESP C++ 六级 | 考点 6：面向对象（堆的封装思路） | 数组模拟堆 |

## 堆是什么

堆是一棵**完全二叉树**，同时满足**堆序性质**：

- **大根堆**：每个节点的值都不小于它的孩子，根是整棵树的最大值。
- **小根堆**：每个节点的值都不大于它的孩子，根是整棵树的最小值。

因为是完全二叉树，堆可以直接用数组存。下标从 1 开始，节点 $i$ 的关系是：

| 关系 | 下标 |
| --- | --- |
| 左孩子 | $2i$ |
| 右孩子 | $2i + 1$ |
| 父节点 | $\lfloor i / 2 \rfloor$ |

数组里看到的值不整体有序，但根一定是这个堆里的最值。这是堆和排序数组的关键区别。

## 两个核心操作

堆的调整围绕两个动作：**上浮**和**下沉**。

### 上浮（插入）

新元素放到数组末尾，然后不断和父节点比较。小根堆里如果它比父节点小就交换，直到比父节点大或者到了根。

```cpp
int heap[100005], sz = 0; // 小根堆

void push(int x) {
    heap[++sz] = x;
    int i = sz;
    while (i > 1 && heap[i] < heap[i / 2]) {
        swap(heap[i], heap[i / 2]);
        i /= 2;
    }
}

一次上浮最多走树高，复杂度 $O(\log n)$。

### 下沉（删除堆顶）

把根和末尾元素交换，删掉末尾，然后让新根不断和较小的孩子比较。小根堆里如果它比孩子大就往下换。

```cpp
void sink(int i) { // 让 heap[i] 往下沉，直到满足堆序
    while (true) {
        int l = 2 * i, r = 2 * i + 1, smallest = i;
        if (l <= sz && heap[l] < heap[smallest]) smallest = l;
        if (r <= sz && heap[r] < heap[smallest]) smallest = r;
        if (smallest == i) break;
        swap(heap[i], heap[smallest]);
        i = smallest;
    }
}

void pop() {
    heap[1] = heap[sz--]; // 末尾元素提到根
    sink(1);              // 再让它沉下去
}

int top() { return heap[1]; } // 堆顶就是最小值，O(1)

### 建堆

把一个无序数组调整成堆，从最后一个非叶子节点开始，依次往前做下沉。

```cpp
void build() {
    for (int i = sz / 2; i >= 1; i--) sink(i);
}

虽然每次下沉是 $O(\log n)$，但对所有节点求和之后总复杂度是 $O(n)$，不是 $O(n \log n)$。这个结论常考：**建堆可以在线性时间内完成**。

## STL 的 priority_queue

竞赛里几乎不用手写堆，直接用 `priority_queue`。

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<int> pq;  // 默认大根堆
    pq.push(3);
    pq.push(1);
    pq.push(4);
    cout << pq.top() << endl; // 4，取最大值
    pq.pop();

    // 小根堆要写全模板参数
    priority_queue<int, vector<int>, greater<int>> minpq;
    minpq.push(3);
    minpq.push(1);
    cout << minpq.top() << endl; // 1

    return 0;
}

`pair` 自带比较规则，先比第一个再比第二个，所以存 `pair<int,int>` 时，默认按第一个值从大到小。

要自定义优先级，可以写比较结构体：

```cpp
struct Node { int id, dis; };

struct Cmp {
    bool operator()(const Node &a, const Node &b) const {
        return a.dis > b.dis; // 想取 dis 最小的，这里写大于
    }
};

priority_queue<Node, vector<Node>, Cmp> pq;

这里的 `>` 是反直觉的：`priority_queue` 的队头是「优先级最高」的元素，而比较函数定义的是排序关系，所以想让小值优先，比较函数里要写 `a.dis > b.dis`。

## 堆的典型应用

- **堆排序**。反复取堆顶输出，时间 $O(n \log n)$，额外空间 $O(1)$。
- **Top K 问题**。求前 $k$ 大的元素，用一个大小为 $k$ 的小根堆，扫描时把比堆顶大的挤进去，最后堆里就是答案。
- **合并果子**。每次取两个最小的合并，用小根堆实现贪心。
- **Dijkstra 最短路优化**。用堆维护当前距离最小的点，复杂度从 $O(V^2)$ 降到 $O(E \log V)$。
- **任务调度**。按优先级取出下一个要执行的任务。

**合并果子**的例子：有 4 堆果子，数量分别是 1、2、3、4，每次合并两堆，代价是两堆数量之和，求最小总代价。

每次取最小的两堆：合并 1 和 2 得 3，代价 3；再合并 3 和 3 得 6，代价 6；合并 4 和 6 得 10，代价 10。总代价 $3 + 6 + 10 = 19$。

这正好是哈夫曼树的构造过程，总代价就是带权路径长度。

## 复杂度

| 操作 | 复杂度 |
| --- | --- |
| 取堆顶 | $O(1)$ |
| 插入 | $O(\log n)$ |
| 删除堆顶 | $O(\log n)$ |
| 建堆 | $O(n)$ |
| 查找任意元素 | $O(n)$ |

堆不擅长查找任意值，也不支持删除任意元素。要删除任意元素，得用能定位元素的高级结构。

## 常见易错点

- 堆不保证整体有序，只保证根是最值，别用堆来做「有序遍历」。
- `priority_queue` 默认是大根堆，小根堆要用 `greater<int>`。
- `priority_queue` 只能访问堆顶，`top()` 之前先判断非空。
- 手写堆时下标从 1 开始，从 0 开始父子下标关系会变。
- 建堆是 $O(n)$，不要以为必须 $O(n \log n)$ 才行。
- 自定义比较函数的方向容易反，写完拿两个数据试一下。
- **该用小根堆的地方写成了默认的大根堆**。合并果子、Top K 都必须显式传 `greater<T>`，忘了 `greater` 会静默给出错误答案。
- **求第 $k$ 大用大根堆**。方向搞反了：求第 $k$ 大要用小根堆（淘汰最小的），求第 $k$ 小要用大根堆。
- **合并果子的答案用了 `int`**。$n$ 和 $a_i$ 都不大，但累加起来的代价会超出 `int`。

## 练习

### 练习 1：合并果子

在线评测练习：[P1422 合并果子](https://dailyup.run/tasks/506)

#### 题目描述

果园里有 $n$ 堆果子，第 $i$ 堆有 $a_i$ 个。每次可以任选两堆合并成一堆，代价为两堆果子数之和。经过 $n - 1$ 次合并后只剩一堆，求**最小总代价**。

#### 输入格式

第一行包含一个正整数 $n$；第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，相邻两个整数之间用一个空格隔开。

#### 输出格式

输出一行一个整数，表示最小总代价。

#### 输入输出样例

输入

```
3
1 2 9

输出

```
15

（先合并 1 和 2，代价 3；再把 3 和 9 合并，代价 12。总代价 $3 + 12 = 15$。）

#### 数据范围

- $1 \le n \le 10^4$，$1 \le a_i \le 2 \times 10^4$。答案可能超出 `int`，请用 `long long`。

#### 题目分析

**这是堆最经典的应用**，也是贪心和堆结合的入门题。

**为什么每次取最小的两堆？** 因为**先被合并的堆会被反复计入后续的代价里**（它变成新堆的一部分，之后每次合并都带着它走）。所以越小的堆应该越早合并、被计入的次数越多——这正好是哈夫曼树的思想。反过来，如果先把大的合并，大数会被反复计入，总代价必然更大。

**为什么必须用堆？** 因为每合并一次就要「重新找出最小的两个」。如果用数组每次排序或线性扫描，复杂度是 $O(n^2 \log n)$ 或 $O(n^2)$；用**小根堆**，插入和取最小都是 $O(\log n)$，总复杂度 $O(n \log n)$。

**代码骨架非常简单**：

1. 把所有果子数推进小根堆；
2. 只要堆里还有 2 个以上元素：弹出最小的两个，求和，把和累加进 `ans`，再把和推回堆；
3. 最后输出 `ans`。

**两个必须注意的点：**

1. **`long long`**。$n = 10^4$、$a_i = 2 \times 10^4$ 时，总代价可能到 $10^9$ 量级甚至更高，且中间累加更容易溢出。堆的元素类型和 `ans` 都用 `long long`。
2. **小根堆的写法**。默认 `priority_queue<long long>` 是**大根堆**，会取出最大的两个，答案完全错。必须写全 `priority_queue<long long, vector<long long>, greater<long long>>`。**这是本题最大的坑**——代码看起来没问题，思路也对，就是忘了 `greater`，答案偏大。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/heap/index.md

`pq.size() > 1` 这个循环条件很关键：只剩一堆时不需要再合并，循环自然结束。**不需要单独处理 $n = 1$ 的情况**，因为一个元素时循环一次都不进，`ans` 保持 0，正是正确答案。

### 练习 2：第 k 大的数（Top K）

#### 题目描述

给定 $n$ 个整数和一个整数 $k$，求**第 $k$ 大**的数（重复的数分别占位，即从大到小排序后第 $k$ 个）。

#### 输入格式

第一行两个整数 $n$ 和 $k$；第二行 $n$ 个整数。

#### 输出格式

输出一个整数，表示第 $k$ 大的数。

#### 输入输出样例

输入

```
5 2
10 4 7 1 9

输出

```
9

#### 数据范围

- $1 \le k \le n \le 10^5$，元素在 `int` 范围内。

#### 题目分析

这题有两条思路，恰好能对比出堆的价值：

**思路一：全排序取第 $k$ 个。** `sort` 一下，复杂度 $O(n \log n)$。$n = 10^5$ 完全够用，**实战中优先这么写**。

**思路二：大小为 $k$ 的小根堆。** 这是 Top K 问题的标准解法，复杂度 $O(n \log k)$：

1. 用小根堆维护「目前见过的最大的 $k$ 个数」；
2. 每读入一个数就推进堆；
3. **如果堆大小超过 $k$，就弹出堆顶（堆里最小的那个）**；
4. 扫完之后，堆里正好是最大的 $k$ 个数，而**堆顶就是第 $k$ 大**。

**为什么小根堆能做到这件事？** 因为小根堆的堆顶是「这 $k$ 个里面最小的」，也就是「第 $k$ 大」。每次新来的数如果比堆顶大，就把它挤掉——堆里始终只保留最大的 $k$ 个。

**什么时候思路二才有优势？**

- 数据是**流式**来的（不能全部存下来再排序），比如从日志里实时找前 $k$ 个最大的；
- $n$ 极大（比如 $10^8$）而 $k$ 很小（比如 10），此时 $O(n \log k)$ 远优于 $O(n \log n)$；
- 内存不够存全部数据。

本题 $n \le 10^5$，两种都能过。但**「用大小为 $k$ 的堆维护 Top K」这个技巧必须掌握**，它是堆最重要的应用模式之一。

**一个容易想错的地方**：求「第 $k$ **大**」用小根堆，求「第 $k$ **小**」用**大根堆**。直觉上是反的，但道理很清楚——要淘汰的是「最不可能是答案的那一端」。求第 $k$ 大时，堆顶是这 $k$ 个里最小的，它最该被更大的数淘汰，所以用小根堆。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/heap/index.md

## 小结

- 堆是完全二叉树加堆序性质，根是全局最值。
- 堆用数组存储，父子下标关系是 $2i$、$2i+1$ 和 $\lfloor i/2 \rfloor$。
- 插入靠上浮，删除堆顶靠下沉，都是 $O(\log n)$；建堆可以 $O(n)$。
- 竞赛里用 `priority_queue`，默认大根堆，小根堆要传 `greater`。
- 堆的典型应用是堆排序、Top K、合并果子和 Dijkstra 优化。
- 合并果子：每次取最小的两个合并，必须用**小根堆**，答案用 `long long`。
- Top K：用**大小为 $k$ 的堆**，超过 $k$ 就弹出堆顶。求第 $k$ 大用小根堆，求第 $k$ 小用大根堆。
- 能全排序解决时优先排序（$O(n \log n)$ 常数小）；数据流式或 $n$ 极大而 $k$ 很小时，才必须用大小为 $k$ 的堆。

Source: https://cppguide.xyz/ds/heap/index.mdx
