第9章 priority_queue 容器详解

priority_queue（优先队列）是 STL 中的容器适配器，底层默认基于 vector + 堆（heap）实现，会自动将元素按优先级排序，保证堆顶元素始终是优先级最高的元素，遵循"堆顶优先"原则。

🎯 本章学习目标

学完本章，你将能够：

理解优先队列的核心思想（按优先级出队）
熟练使用 priority_queue 的基本操作（push、pop、top）
掌握大顶堆和小顶堆的定义与使用
理解优先队列的底层实现（二叉堆）
掌握自定义比较函数的写法
能用优先队列解决 TopK 等经典问题
理解优先队列与普通队列、set 的区别
根据场景选择合适的优先队列配置

🗺️ 本章知识图谱

priority_queue 优先队列
├── 核心特性
│   ├── 按优先级排序
│   ├── 容器适配器
│   ├── 仅堆顶操作
│   └── 无迭代器
├── 基本用法
│   ├── 定义与头文件
│   ├── push（入队）
│   ├── pop（出队）
│   ├── top（访问堆顶）
│   ├── empty（判空）
│   └── size（大小）
├── 堆的类型
│   ├── 大顶堆（默认）
│   ├── 小顶堆（greater）
│   └── 自定义比较
├── 底层原理
│   ├── 二叉堆结构
│   ├── 上滤（插入）
│   ├── 下滤（删除）
│   └── 建堆过程
├── 经典应用
│   ├── TopK 问题
│   ├── 任务调度
│   ├── 合并 K 个有序链表
│   └── 哈夫曼编码
├── 注意事项
│   ├── 不可遍历
│   ├── 不能修改元素
│   └── 空堆访问 top 崩溃
└── 适用场景与选型

一、priority_queue 核心特性

🍎 生活比喻：priority_queue 就像医院的急诊室——不是先来的先看，而是病情最严重（优先级最高）的病人先看。每个病人来的时候，护士会根据病情安排到合适的位置，医生每次都先处理最紧急的那个。

堆结构：底层默认是大顶堆（最大值优先），可自定义排序规则；
自动排序：插入元素时自动调整堆结构，保证优先级有序；
受限访问：只能访问**堆顶（top）**元素，不能访问其他元素；
高效操作：插入、删除堆顶效率为 O(log n)；
无迭代器：不支持遍历，无法访问非堆顶元素。

🔥 高频考点：优先队列的底层是堆、插入删除 O(log n)、默认大顶堆，这些是选择题的高频考点。

二、priority_queue 基础用法

使用 priority_queue 需包含 <queue> 头文件（和 queue 同一个头文件）。

cpp

#include <iostream>
#include <queue>    // 优先队列头文件
#include <vector>
using namespace std;

int main() {
    // 1. 默认大顶堆（最大值优先）
    priority_queue<int> pq;
    
    // 2. 插入元素（自动调整堆结构）
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    
    // 3. 访问堆顶（优先级最高的元素）
    cout << "堆顶元素：" << pq.top() << endl;  // 输出 50
    
    // 4. 删除堆顶元素（自动调整堆结构）
    pq.pop();
    cout << "删除后堆顶：" << pq.top() << endl; // 输出 30
    
    // 5. 遍历输出（只能逐个取堆顶，会清空队列）
    cout << "依次出队：";
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    // 输出：30 20 10
    cout << endl;
    
    // 6. 常用操作
    cout << "队列大小：" << pq.size() << endl;
    cout << "是否为空：" << (pq.empty() ? "是" : "否") << endl;
    
    return 0;
}

操作汇总表

操作	语法	说明	时间复杂度
插入	push(元素)	插入元素并自动调整堆	O(log n)
删除堆顶	pop()	删除优先级最高的元素，无返回值	O(log n)
访问堆顶	top()	返回堆顶元素（不删除），需确保非空	O(1)
判空	empty()	为空返回 true，否则返回 false	O(1)
获取大小	size()	返回元素个数	O(1)
清空	无 clear()	需循环 pop()	O(n log n)

💡 小技巧：priority_queue 没有 clear() 方法，清空的方法是 while (!pq.empty()) pq.pop();，或者用技巧 priority_queue<int>().swap(pq);。

三、大顶堆与小顶堆

1. 大顶堆（默认）

默认情况下，priority_queue 是大顶堆，值越大优先级越高，堆顶是最大值。

cpp

priority_queue<int> pq;  // 默认大顶堆
pq.push(3);
pq.push(1);
pq.push(5);
pq.push(2);
// 堆顶是 5，依次出队顺序：5 3 2 1

2. 小顶堆

如果需要值越小优先级越高（小顶堆），定义时需要指定底层容器和比较函数：

cpp

// 小顶堆定义方式：priority_queue<类型, 底层容器, 比较函数>
priority_queue<int, vector<int>, greater<int>> pq_min;
pq_min.push(3);
pq_min.push(1);
pq_min.push(5);
// 堆顶是 1，依次出队顺序：1 3 5

⚠️ 易错点：小顶堆的定义语法比较复杂，很多同学记不住。记住格式：priority_queue<T, vector<T>, greater<T>>，三个参数分别是：元素类型、底层容器、比较方式。

3. 完整对比示例

cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int> max_heap;          // 大顶堆
    priority_queue<int, vector<int>, greater<int>> min_heap;  // 小顶堆
    
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
    for (int x : arr) {
        max_heap.push(x);
        min_heap.push(x);
    }
    
    cout << "大顶堆出队（从大到小）：";
    while (!max_heap.empty()) {
        cout << max_heap.top() << " ";
        max_heap.pop();
    }
    cout << endl;  // 输出：9 6 5 4 3 2 1 1
    
    cout << "小顶堆出队（从小到大）：";
    while (!min_heap.empty()) {
        cout << min_heap.top() << " ";
        min_heap.pop();
    }
    cout << endl;  // 输出：1 1 2 3 4 5 6 9
    
    return 0;
}

🔥 高频考点：默认大顶堆、小顶堆需要用 greater，这是选择题和填空题的常考点。

四、底层原理：二叉堆（进阶）

priority_queue 的底层是二叉堆（binary heap），这是一种完全二叉树，用数组存储。

1. 大顶堆的性质

是一棵完全二叉树；
每个节点的值都大于等于它的左右子节点；
根节点（堆顶）是整个堆中的最大值。

2. 数组表示

因为是完全二叉树，可以用数组来存储：

父节点下标为 i，左子节点下标为 2*i+1，右子节点下标为 2*i+2；
子节点下标为 i，父节点下标为 (i-1)/2。

3. 插入操作（上滤）

把新元素放到数组末尾（堆的最后一个位置）；
与父节点比较，如果比父节点大（大顶堆），就和父节点交换；
重复第 2 步，直到父节点更大或到达堆顶。

时间复杂度：O(log n)

4. 删除堆顶操作（下滤）

把堆顶元素保存起来（作为返回值）；
把最后一个元素移到堆顶；
与左右子节点中较大的那个比较，如果比子节点小，就交换；
重复第 3 步，直到子节点都更小或到达叶子节点。

时间复杂度：O(log n)

🍎 生活比喻：插入就像新员工入职——先坐到最底层的位置，然后发现自己比上级厉害，就跟上级交换位置，一直升到合适的位置。删除堆顶就像CEO 离职——把最底层的员工拉到 CEO 位置，然后发现他管不了下属，就和更厉害的下属交换，一直降到合适的位置。

五、自定义比较（进阶）

除了默认的大顶堆和小顶堆，priority_queue 还支持自定义比较规则，用于复杂类型（如结构体、pair）。

示例：自定义结构体的比较

cpp

#include <iostream>
#include <queue>
#include <string>
using namespace std;

// 学生结构体：姓名 + 分数
struct Student {
    string name;
    int score;
    Student(string n, int s) : name(n), score(s) {}
};

// 自定义比较：分数高的优先级高（大顶堆）
struct cmp_score {
    bool operator()(const Student& a, const Student& b) {
        return a.score < b.score;  // 分数高的在前面
    }
};

int main() {
    priority_queue<Student, vector<Student>, cmp_score> pq;
    pq.push(Student("张三", 85));
    pq.push(Student("李四", 95));
    pq.push(Student("王五", 90));
    
    while (!pq.empty()) {
        cout << pq.top().name << "：" << pq.top().score << "分" << endl;
        pq.pop();
    }
    // 输出：
    // 李四：95分
    // 王五：90分
    // 张三：85分
    
    return 0;
}

⚠️ 易错点：priority_queue 的比较函数写法和 sort 正好相反！sort 中 return a < b 是升序，但 priority_queue 中 return a < b 是大顶堆（大的在前）。记忆口诀：priority_queue 的比较函数定义的是"谁的优先级更低"。

六、与其他容器对比

特性	priority_queue	set	queue
顺序	按优先级	按 key 排序	按插入顺序（FIFO）
插入	O(log n)	O(log n)	O(1)
删除	O(log n)（删堆顶）	O(log n)	O(1)（删队头）
访问	只能访问堆顶	可查找任意元素	只能访问头尾
遍历	不支持	支持	不支持
底层	二叉堆	红黑树	deque
适用场景	TopK、任务调度	去重、查找	排队、BFS

七、常见误区与注意事项

⚠️ 易错点 1：认为 priority_queue 是 queue 的一种。虽然名字里有 queue，但它和普通 queue 的出队规则完全不同。普通 queue 是 FIFO，priority_queue 是按优先级出队。

⚠️ 易错点 2：小顶堆的写法记不住。记住模板：priority_queue<T, vector<T>, greater<T>>，三个参数缺一不可。

⚠️ 易错点 3：以为可以遍历。priority_queue 没有迭代器，不能遍历所有元素，只能通过 top() 访问堆顶，或者依次弹出。

⚠️ 易错点 4：空堆调用 top()/pop()。和 stack、queue 一样，空的优先队列调用 top() 或 pop() 会导致未定义行为（程序崩溃）。

⚠️ 易错点 5：可以修改元素。priority_queue 的元素不能直接修改（因为会破坏堆结构），如果需要修改，只能先弹出旧元素，再插入新元素。

⚠️ 易错点 6：比较函数和 sort 一样。priority_queue 的比较函数逻辑和 sort 是反的！less<T> 对应大顶堆（大的在前），greater<T> 对应小顶堆（小的在前）。

八、经典应用场景

1. TopK 问题（算法题高频）

求数组中第 K 大的元素，或前 K 大的元素。这是优先队列最经典的应用。

**思路：**维护一个大小为 K 的小顶堆，遍历数组，如果当前元素比堆顶大，就弹出堆顶，插入当前元素。遍历结束后，堆顶就是第 K 大的元素。

cpp

// 求第 K 大的元素
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> min_heap;
    for (int x : nums) {
        min_heap.push(x);
        if (min_heap.size() > k) {
            min_heap.pop();
        }
    }
    return min_heap.top();
}

🔥 高频考点：TopK 问题是面试和竞赛的必考题，必须掌握用小顶堆的解法。

2. 任务调度

按优先级处理任务，优先级高的任务先执行。

3. 合并 K 个有序链表

用小顶堆维护 K 个链表的当前节点，每次取出最小的节点加入结果。

4. 哈夫曼编码

用优先队列每次取出两个权值最小的节点合并。

九、🔖 本章小结

priority_queue 是一种按优先级排序的容器适配器，底层是二叉堆，插入删除都是 O(log n)。默认是大顶堆，用 greater<T> 可以变成小顶堆。它最经典的应用是 TopK 问题，也是任务调度、合并有序链表等问题的高效解法。使用时需注意：只能访问堆顶、不可遍历、空堆不能调用 top/pop。

十、📝 实战练习

练习题 1（选择题）

题目： priority_queue 的底层数据结构是？

A. 红黑树 B. 二叉堆 C. 双向链表 D. 哈希表

🔑 点击查看答案与解析

答案： B

**解析：**priority_queue 底层是二叉堆（默认大顶堆），通常用 vector 作为底层容器。A 是 set/map 的底层结构，C 是 list 的底层结构，D 是 unordered_set/unordered_map 的底层结构。

练习题 2（判断题）

题目： priority_queue 默认是小顶堆（值越小优先级越高）（）

🔑 点击查看答案与解析

答案： 错误

**解析：**priority_queue 默认是大顶堆，值越大优先级越高，堆顶是最大值。如果需要小顶堆，要显式指定 greater<T>，如 priority_queue<int, vector<int>, greater<int>>。

练习题 3（选择题）

题目： priority_queue 的 push 操作时间复杂度是？

A. O(1) B. O(log n) C. O(n) D. O(n log n)

🔑 点击查看答案与解析

答案： B

**解析：**priority_queue 底层是二叉堆，插入元素需要进行"上滤"操作，最坏情况下要从堆底一直交换到堆顶，时间复杂度是 O(log n)。pop 操作也是 O(log n)。

练习题 4（程序阅读题）

题目： 阅读以下代码，写出输出结果：

cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(5);
    pq.push(2);
    pq.push(8);
    pq.push(1);
    cout << pq.top() << " ";
    pq.pop();
    cout << pq.top() << endl;
    return 0;
}

🔑 点击查看答案与解析

答案： 1 2

**解析：**这是一个小顶堆（因为用了 greater<int>），元素越小优先级越高。

插入 5、2、8、1 后，堆顶是最小的 1
top() 输出 1
pop() 删除 1 后，新的堆顶是 2
top() 输出 2

最终输出：1 2

练习题 5（选择题）

题目： 以下关于 priority_queue 的说法，错误的是？

A. priority_queue 支持随机访问任意元素 B. priority_queue 的底层默认是 vector C. priority_queue 没有迭代器，不能遍历 D. priority_queue 的 top() 返回堆顶元素

🔑 点击查看答案与解析

答案： A

解析：

A 错误：priority_queue 只能访问堆顶元素，不能随机访问其他元素
B 正确：priority_queue 默认底层容器是 vector
C 正确：priority_queue 没有迭代器，不能遍历
D 正确：top() 返回优先级最高的堆顶元素

练习题 6（编程题）

题目： 输入 n 个整数，输出其中前 K 大的数（从大到小输出）。

**输入格式：**第一行两个整数 n 和 k，第二行 n 个整数 **输出格式：**一行，前 K 大的数，从大到小排列

样例输入：

8 3
3 1 4 1 5 9 2 6

样例输出：

9 6 5

🔑 点击查看答案与解析

参考代码（方法一：大顶堆，全部入队后取前 K 个）：

cpp

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

int main() {
    int n, k;
    cin >> n >> k;
    priority_queue<int> pq;  // 大顶堆
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }
    
    // 依次取出前 K 个
    for (int i = 0; i < k; i++) {
        if (i > 0) cout << " ";
        cout << pq.top();
        pq.pop();
    }
    cout << endl;
    
    return 0;
}

参考代码（方法二：小顶堆维护 TopK，空间更优）：

cpp

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    priority_queue<int, vector<int>, greater<int>> min_heap;  // 小顶堆
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        min_heap.push(x);
        if (min_heap.size() > k) {
            min_heap.pop();  // 堆中超过 K 个，弹出最小的
        }
    }
    
    // 小顶堆里存的是前 K 大的，需要倒序输出
    vector<int> result;
    while (!min_heap.empty()) {
        result.push_back(min_heap.top());
        min_heap.pop();
    }
    reverse(result.begin(), result.end());
    
    for (int i = 0; i < result.size(); i++) {
        if (i > 0) cout << " ";
        cout << result[i];
    }
    cout << endl;
    
    return 0;
}

解析：

方法一：最简单，全部放入大顶堆，然后取前 K 个。时间 O(n log n)，空间 O(n)。
方法二：更优，用小顶堆维护大小为 K 的窗口。时间 O(n log k)，空间 O(k)。当 n 很大而 k 很小时，方法二优势明显。

这就是经典的 TopK 问题，方法二是面试中的标准最优解。

练习题 7（编程题）

题目： 使用优先队列对一个数组进行排序（从小到大）。

**输入格式：**第一行一个整数 n，第二行 n 个整数 **输出格式：**一行，排序后的整数

样例输入：

5
3 1 4 1 5

样例输出：

1 1 3 4 5

🔑 点击查看答案与解析

参考代码：

cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 用小顶堆，出来就是从小到大
    priority_queue<int, vector<int>, greater<int>> min_heap;
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        min_heap.push(x);
    }
    
    // 依次出队输出
    while (!min_heap.empty()) {
        cout << min_heap.top();
        min_heap.pop();
        if (!min_heap.empty()) cout << " ";
    }
    cout << endl;
    
    return 0;
}

**解析：**这就是堆排序（heap sort）的基本思想。把所有元素放入小顶堆，然后依次弹出，就得到了从小到大排序的结果。时间复杂度 O(n log n)，和 sort 函数一样。

不过实际编程中直接用 sort 更方便，这道题主要是帮助理解优先队列的原理。

十一、📊 考点总结表

知识点	重要程度	出题形式	易错点
底层是二叉堆	⭐⭐⭐⭐	选择题	与红黑树混淆
默认大顶堆	⭐⭐⭐⭐⭐	选择题、判断题	以为默认是小顶堆
小顶堆写法（greater）	⭐⭐⭐⭐⭐	选择题、编程题	语法记不住
push/pop 时间 O(log n)	⭐⭐⭐⭐	选择题	以为是 O(1)
只能访问堆顶	⭐⭐⭐	选择题、判断题	以为可以随机访问
无迭代器、不可遍历	⭐⭐⭐	判断题	试图遍历
TopK 问题	⭐⭐⭐⭐⭐	编程题	不会用小顶堆维护
比较函数与 sort 相反	⭐⭐⭐	选择题、编程题	搞反大小顶堆
空堆调用 top/pop 崩溃	⭐⭐⭐	判断题	忘记判空

⭐ 必背速记卡

┌──────────────────────────────────────┐
│  priority_queue 必背速记卡            │
├──────────────────────────────────────┤
│  1. 优先队列，底层是二叉堆             │
│  2. 默认大顶堆，值越大优先级越高       │
│  3. 小顶堆写法：greater<T> + vector<T> │
│  4. push/pop 时间复杂度 O(log n)      │
│  5. top() 访问堆顶，O(1)              │
│  6. 只能访问堆顶，不能遍历             │
│  7. 没有迭代器，没有 clear()          │
│  8. 空堆调用 top/pop 会崩溃           │
│  9. 经典应用：TopK、任务调度           │
│  10. 比较函数和 sort 逻辑相反         │
└──────────────────────────────────────┘

第9章 priority_queue 容器详解 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、priority_queue 核心特性 ​

二、priority_queue 基础用法 ​

操作汇总表 ​

三、大顶堆与小顶堆 ​

1. 大顶堆（默认） ​

2. 小顶堆 ​

3. 完整对比示例 ​

四、底层原理：二叉堆（进阶） ​

1. 大顶堆的性质 ​

2. 数组表示 ​

3. 插入操作（上滤） ​

4. 删除堆顶操作（下滤） ​

五、自定义比较（进阶） ​

示例：自定义结构体的比较 ​

六、与其他容器对比 ​

七、常见误区与注意事项 ​

八、经典应用场景 ​

1. TopK 问题（算法题高频） ​

2. 任务调度 ​

3. 合并 K 个有序链表 ​

4. 哈夫曼编码 ​

九、🔖 本章小结 ​

十、📝 实战练习 ​

练习题 1（选择题） ​

练习题 2（判断题） ​

练习题 3（选择题） ​

练习题 4（程序阅读题） ​

练习题 5（选择题） ​

练习题 6（编程题） ​

练习题 7（编程题） ​

十一、📊 考点总结表 ​

⭐ 必背速记卡 ​

第9章 priority_queue 容器详解

🎯 本章学习目标

🗺️ 本章知识图谱

一、priority_queue 核心特性

二、priority_queue 基础用法

操作汇总表

三、大顶堆与小顶堆

1. 大顶堆（默认）

2. 小顶堆

3. 完整对比示例

四、底层原理：二叉堆（进阶）

1. 大顶堆的性质

2. 数组表示

3. 插入操作（上滤）

4. 删除堆顶操作（下滤）

五、自定义比较（进阶）

示例：自定义结构体的比较

六、与其他容器对比

七、常见误区与注意事项

八、经典应用场景

1. TopK 问题（算法题高频）

2. 任务调度

3. 合并 K 个有序链表

4. 哈夫曼编码

九、🔖 本章小结

十、📝 实战练习

练习题 1（选择题）

练习题 2（判断题）

练习题 3（选择题）

练习题 4（程序阅读题）

练习题 5（选择题）

练习题 6（编程题）

练习题 7（编程题）

十一、📊 考点总结表

⭐ 必背速记卡