一、什么是优先队列优先队列就是一个会自动排序的队列。普通队列 vs 优先队列// 普通队列先进先出 queueint q; q.push(3); q.push(1); q.push(2); // 取出顺序3, 1, 2 // 优先队列按大小排序 priority_queueint pq; pq.push(3); pq.push(1); pq.push(2); // 取出顺序3, 2, 1从大到小优先队列的基本用法1. 头文件#include queue2. 声明方式// 方式1最大堆默认 priority_queueint pq1; // 最大的元素在顶部 // 方式2最小堆 priority_queueint, vectorint, greaterint pq2; // 最小的元素在顶部 // 方式3自定义比较 priority_queueNode*, vectorNode*, Compare pq3; // 按自定义规则排序三、常用操作priority_queueint pq; // 添加元素 pq.push(10); pq.push(5); pq.push(20); // 访问顶部元素 int top pq.top(); // 返回20最大值 // 删除顶部元素 pq.pop(); // 删除20 // 判断是否为空 if (pq.empty()) { } // 获取大小 int size pq.size(); // 2四、三种声明方式详解方式1最大堆默认priority_queueint pq; // 等价于 priority_queueint, vectorint, lessint pq;特点最大的元素在顶部pq.push(3); pq.push(1); pq.push(2); cout pq.top(); // 输出 3方式2最小堆priority_queueint, vectorint, greaterint pq;特点最小的元素在顶部pq.push(3); pq.push(1); pq.push(2); cout pq.top(); // 输出 1方式3自定义类型struct Node { int weight; int ascii; }; struct Compare { bool operator()(Node a, Node b) { // 返回true表示a的优先级低于b if (a.weight ! b.weight) { return a.weight b.weight; // 权值小的优先 } return a.ascii b.ascii; // ASCII小的优先 } }; priority_queueNode, vectorNode, Compare pq;优先队列本质上就是一种“每次都能快速取出最大或最小元素”的数据结构你可以把它理解成一个“自动排序的队列”但它不是完全排序的而是始终保证队头元素是当前优先级最高的那个在 C 里默认是大根堆也就是每次取出最大值。先说最核心的特点普通队列是先进先出而优先队列是“优先级高的先出”至于谁优先级高是由比较规则决定的底层实现一般是堆heap所以插入和删除的时间复杂度都是 O(log n)查询堆顶是 O(1)。C 中的基本用法很固定定义一个优先队列 priority_queue pq这样默认就是大根堆如果你想要小根堆就要写成 priority_queueint, vector, greater pq这个写法的意思是用 vector 存数据用 greater 作为比较函数让小的优先出来。常用操作就几个push(x) 把元素加入队列pop() 删除队头元素注意不会返回值top() 查看当前队头empty() 判断是否为空size() 查看元素个数这些操作和普通队列类似但语义不同。再说一个非常常见的用法就是存 pair比如在 Dijkstra 里我们通常存 pair距离, 节点编号并且用小根堆这样每次取出的都是当前距离最小的点写法是 priority_queuepairlong long,int, vectorpairlong long,int, greaterpairlong long,int pq这里的比较是先比较 first如果相等再比较 second。优先队列最经典的应用有几个第一是最短路径Dijkstra每次取当前距离最小的点第二是哈夫曼树合并果子每次取最小的两个数第三是一些“动态维护最大/最小值”的问题比如不断加入元素并随时查询最大值。最后讲一个容易踩的坑priority_queue 不能像 vector 一样遍历它不支持随机访问如果你想看所有元素只能不断 pop另外pop 只删除元素不返回值一定要先 top 再 pop还有一点就是如果你自定义结构体一定要写比较规则否则编译会报错。总结一句优先队列就是一个“随时能拿到当前最优元素”的工具核心是堆结构时间复杂度 O(log n)一旦题目出现“反复取最值”基本就可以考虑它。
【数据结构与算法】优先队列
一、什么是优先队列优先队列就是一个会自动排序的队列。普通队列 vs 优先队列// 普通队列先进先出 queueint q; q.push(3); q.push(1); q.push(2); // 取出顺序3, 1, 2 // 优先队列按大小排序 priority_queueint pq; pq.push(3); pq.push(1); pq.push(2); // 取出顺序3, 2, 1从大到小优先队列的基本用法1. 头文件#include queue2. 声明方式// 方式1最大堆默认 priority_queueint pq1; // 最大的元素在顶部 // 方式2最小堆 priority_queueint, vectorint, greaterint pq2; // 最小的元素在顶部 // 方式3自定义比较 priority_queueNode*, vectorNode*, Compare pq3; // 按自定义规则排序三、常用操作priority_queueint pq; // 添加元素 pq.push(10); pq.push(5); pq.push(20); // 访问顶部元素 int top pq.top(); // 返回20最大值 // 删除顶部元素 pq.pop(); // 删除20 // 判断是否为空 if (pq.empty()) { } // 获取大小 int size pq.size(); // 2四、三种声明方式详解方式1最大堆默认priority_queueint pq; // 等价于 priority_queueint, vectorint, lessint pq;特点最大的元素在顶部pq.push(3); pq.push(1); pq.push(2); cout pq.top(); // 输出 3方式2最小堆priority_queueint, vectorint, greaterint pq;特点最小的元素在顶部pq.push(3); pq.push(1); pq.push(2); cout pq.top(); // 输出 1方式3自定义类型struct Node { int weight; int ascii; }; struct Compare { bool operator()(Node a, Node b) { // 返回true表示a的优先级低于b if (a.weight ! b.weight) { return a.weight b.weight; // 权值小的优先 } return a.ascii b.ascii; // ASCII小的优先 } }; priority_queueNode, vectorNode, Compare pq;优先队列本质上就是一种“每次都能快速取出最大或最小元素”的数据结构你可以把它理解成一个“自动排序的队列”但它不是完全排序的而是始终保证队头元素是当前优先级最高的那个在 C 里默认是大根堆也就是每次取出最大值。先说最核心的特点普通队列是先进先出而优先队列是“优先级高的先出”至于谁优先级高是由比较规则决定的底层实现一般是堆heap所以插入和删除的时间复杂度都是 O(log n)查询堆顶是 O(1)。C 中的基本用法很固定定义一个优先队列 priority_queue pq这样默认就是大根堆如果你想要小根堆就要写成 priority_queueint, vector, greater pq这个写法的意思是用 vector 存数据用 greater 作为比较函数让小的优先出来。常用操作就几个push(x) 把元素加入队列pop() 删除队头元素注意不会返回值top() 查看当前队头empty() 判断是否为空size() 查看元素个数这些操作和普通队列类似但语义不同。再说一个非常常见的用法就是存 pair比如在 Dijkstra 里我们通常存 pair距离, 节点编号并且用小根堆这样每次取出的都是当前距离最小的点写法是 priority_queuepairlong long,int, vectorpairlong long,int, greaterpairlong long,int pq这里的比较是先比较 first如果相等再比较 second。优先队列最经典的应用有几个第一是最短路径Dijkstra每次取当前距离最小的点第二是哈夫曼树合并果子每次取最小的两个数第三是一些“动态维护最大/最小值”的问题比如不断加入元素并随时查询最大值。最后讲一个容易踩的坑priority_queue 不能像 vector 一样遍历它不支持随机访问如果你想看所有元素只能不断 pop另外pop 只删除元素不返回值一定要先 top 再 pop还有一点就是如果你自定义结构体一定要写比较规则否则编译会报错。总结一句优先队列就是一个“随时能拿到当前最优元素”的工具核心是堆结构时间复杂度 O(log n)一旦题目出现“反复取最值”基本就可以考虑它。
