priority_queue优先队列
目录
1. 最短路径算法（Dijkstra算法）
应用场景：
优先队列的作用：
2. 最小生成树算法（Prim算法）
应用场景：
优先队列的作用：
3. 哈夫曼编码（Huffman Coding）
应用场景：
优先队列的作用：
4. 合并K个有序链表（Merge K Sorted Lists）
应用场景：
优先队列的作用：
5.贪心算法中的应用
应用场景：
优先队列的作用：
6. 动态中位数维护
应用场景：
优先队列的作用：
7.石子合并问题（Stone Merging Problem）
1. 应用场景
最近发现优先队列真的超级好用，让我来总结一下（激动到起飞.......)。
One What is priority_queue? (什么是优先队列）
一堆可以进行比较的数据元素，被赋予一定的优先级，谁的优先级高，先处理谁，要是优先级一样高，通常按照它们进入队列的顺序进行处理（具体取决于代码怎么实现的）。
Two The base operation.（基础操作）
以名称为pq的优先队列简单介绍一下。
1.在c++中priority_queue模板类定义在<queue>头文件中。
2. pq.push(元素); 将一个元素推进pq队列中。
3.pq.top(); 优先队列顶部元素（优先级最高的元素）。
4.pq.pop;将优先队列最顶部的元素删除,要先取出来（pq.top()),再删除。这两步操作要同步进行。
5.pq.size();告诉你这个优先队列有多大 。
6.pq.empty();告诉你这个优先队列是不是空的，true表示是空的，false表示不空的。
Three Definition methods(定义方式）
1.普通版： priority_queue<long long> pq;
2.升序版：priority_queue<元素数据类型，盛装元素的容器或数组，greatr<元素数据类型>>
举个栗子：priority<int,vector<int>,greater<int>> pq;
3.降序版：priority_queue<int,vector<int>,less<int>> pq;(priority_queue默认降序）
4.存储自定义结构体或类时，还要搞一个比较器来定义元素的优先级。
存储自定义的方式的5种主要形式：
<1>结构体：
- 默认访问级别：公有（
public） - 这意味着，除非明确指定，结构体中的成员变量和成员函数都是公有的，外部代码可以直接访问它们。
#include <iostream>
using namespace std;
// 使用 struct 定义
struct PointStruct {
int x;
int y;
};
int main(){
PointStruct ps;
ps.x = 10; // 可以直接访问和修改
ps.y = 20;
cout << "PointStruct: (" << ps.x << ", " << ps.y << ")\n";
return 0;
}
PointStruct: (10, 20)
<2>类：
- 默认访问级别：私有（
private） - 这意味着，除非明确指定，类中的成员变量和成员函数都是私有的，外部代码无法直接访问它们。
#include <iostream>
#include <string>
using namespace std;
// 使用 class 定义
class PointClass {
private:
int x; // 私有成员变量
int y; // 私有成员变量
public:
// 构造函数
PointClass(int a = 0, int b = 0) : x(a), y(b) {}
// 公有成员函数：设置 x 的值
void setX(int a) {
x = a;
}
// 公有成员函数：设置 y 的值
void setY(int b) {
y = b;
}
// 公有成员函数：获取 x 的值
int getX() const {
return x;
}
// 公有成员函数：获取 y 的值
int getY() const {
return y;
}
// 公有成员函数：打印坐标
void print() const {
cout << "PointClass: (" << x << ", " << y << ")\n";
}
};
int main(){
// 使用 struct
PointStruct ps;
ps.x = 10; // 可以直接访问和修改
ps.y = 20;
cout << "PointStruct: (" << ps.x << ", " << ps.y << ")\n";
// 使用 class
PointClass pc; // 使用默认构造函数
// pc.x = 30; // 错误：'x' 是私有的，无法直接访问
// pc.y = 40; // 错误：'y' 是私有的，无法直接访问
// 通过公有成员函数设置值
pc.setX(30);
pc.setY(40);
pc.print();
// 通过公有成员函数获取值
cout << "PointClass x: " << pc.getX() << ", y: " << pc.getY() << "\n";
return 0;
}
PointStruct: (10, 20)
PointClass: (30, 40)
PointClass x: 30, y: 40
<3>类+结构体：
#include <iostream>
using namespace std;
// 使用struct定义
struct PointStruct {
int x;
int y;
};
// 使用class定义
class PointClass {
public:
int x;
int y;
};
int main(){
PointStruct ps;
ps.x = 10; // 可以直接访问
ps.y = 20;
cout << "PointStruct: (" << ps.x << ", " << ps.y << ")\n";
PointClass pc;
pc.x = 30; // 需要public访问权限
pc.y = 40;
cout << "PointClass: (" << pc.x << ", " << pc.y << ")\n";
return 0;
}
PointStruct: (10, 20)
PointClass: (30, 40)
<4>使用指针或引用
有时，为了节省内存或管理大型数据结构，可以在优先队列中存储指针（如Node*）或引用。
#include<bits/stdc++.h>
using namespace std;
// 定义任务结构体
struct Task {
int priority;
string name;
Task(int p, string n) : priority(p), name(n) {}
};
// 定义比较器
struct CompareTaskPtr {
bool operator()(const Task* a, const Task* b) const {
return a->priority < b->priority; // 优先级高的先出
}
};
int main(){
// 定义优先队列，存储Task*，最大堆
priority_queue<Task*, vector<Task*>, CompareTaskPtr> pq;
// 动态分配任务并插入优先队列
pq.push(new Task(3, "Task A"));
pq.push(new Task(1, "Task B"));
pq.push(new Task(4, "Task C"));
pq.push(new Task(2, "Task D"));
// 依次取出任务并释放内存
while(!pq.empty()){
Task* t = pq.top();
cout << "Priority: " << t->priority << ", Name: " << t->name << endl;
pq.pop();
delete t; // 释放动态分配的内存
}
return 0;
}
Priority: 4, Name: Task C
Priority: 3, Name: Task A
Priority: 2, Name: Task D
Priority: 1, Name: Task B
<5>使用枚举类型（Enums）
当需要基于预定义的优先级级别进行排序时，可以使用枚举类型。除了上述常见的struct、class、pair和tuple，优先队列还可以存储其他类型的数据，具体取决于问题的需求。优先级任务：高，中，低。
#include<bits/stdc++.h>
using namespace std;
// 定义优先级枚举
enum Priority { LOW = 1, MEDIUM = 2, HIGH = 3 };
// 定义任务结构体
struct Task {
Priority priority;
string name;
Task(Priority p, string n) : priority(p), name(n) {}
};
// 定义比较器
struct CompareTask {
bool operator()(const Task& a, const Task& b) const {
return a.priority < b.priority; // 高优先级先出
}
};
int main(){
// 定义优先队列，使用自定义比较器
priority_queue<Task, vector<Task>, CompareTask> pq;
// 插入任务
pq.emplace(HIGH, "Task A");
pq.emplace(LOW, "Task B");
pq.emplace(MEDIUM, "Task C");
pq.emplace(HIGH, "Task D");
// 依次取出任务
while(!pq.empty()){
Task t = pq.top();
cout << "Priority: " << t.priority << ", Name: " << t.name << endl;
pq.pop();
}
return 0;
}
Priority: 3, Name: Task A
Priority: 3, Name: Task D
Priority: 2, Name: Task C
Priority: 1, Name: Task B
比较器的三种种主要形式：
<1> 重载全局的 operator，这种方法会影响所有Node类型的比较，不仅限于优先队列。
#include<bits/stdc++.h>
using namespace std;
struct Node {
int x, y;
Node(int a = 0, int b = 0) : x(a), y(b) {}
};
// 重载全局的 operator<
bool operator<(const Node& a, const Node& b){
if(a.x == b.x)
return a.y > b.y; // y 小的优先
return a.x > b.x; // x 小的优先
}
int main(){
// 定义一个存储 Node 的优先队列（最大堆）
priority_queue<Node> pq;
// 插入元素
pq.push(Node(5, 3));
pq.push(Node(2, 8));
pq.push(Node(5, 1));
pq.push(Node(3, 7));
pq.push(Node(2, 4));
pq.push(Node(5, 6));
pq.push(Node(1, 9));
pq.push(Node(3, 2));
pq.push(Node(1, 5));
pq.push(Node(4, 0));
// 依次取出元素
while(!pq.empty()){
Node top = pq.top();
cout << top.x << " " << top.y << endl;
pq.pop();
}
return 0;
}
1 5
1 9
2 4
2 8
3 2
3 7
4 0
5 1
5 3
5 6
<2> 定义自定义比较器结构体，这种方法更具封装性，不会影响全局的Node比较，仅作用于特定的优先队列。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int x, y;
Node(int a = 0, int b = 0) : x(a), y(b) {}
};
// 定义自定义比较器
struct cmp {
bool operator()(const Node& a, const Node& b) const {
//按引用传递：为了提高效率，比较器的参数最好按const引用传递，并将operator()声明为const成员函数。
if(a.x == b.x)
return a.y > b.y; // y 小的优先
return a.x > b.x; // x 小的优先
}
};
int main(){
// 定义一个存储 Node 的优先队列（最小堆）
priority_queue<Node, vector<Node>, cmp> pq;
// 插入元素
pq.push(Node(5, 3));
pq.push(Node(2, 8));
pq.push(Node(5, 1));
pq.push(Node(3, 7));
pq.push(Node(2, 4));
pq.push(Node(5, 6));
pq.push(Node(1, 9));
pq.push(Node(3, 2));
pq.push(Node(1, 5));
pq.push(Node(4, 0));
// 依次取出元素
while(!pq.empty()){
Node top = pq.top();
cout << top.x << " " << top.y << endl;
pq.pop();
}
return 0;
}
<3>Lambda 表达式 （c++及以上版本）
#include<bits/stdc++.h>
using namespace std;
struct Node {
int x, y;
Node(int a = 0, int b = 0) : x(a), y(b) {}
};
int main(){
// 定义一个存储 Node 的优先队列（最小堆），使用 Lambda 比较器
auto cmp = [](const Node& a, const Node& b) -> bool {
if(a.x == b.x)
return a.y > b.y; // y 小的优先
return a.x > b.x; // x 小的优先
};
priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);
// 插入元素
pq.push(Node(5, 3));
pq.push(Node(2, 8));
pq.push(Node(5, 1));
pq.push(Node(3, 7));
pq.push(Node(2, 4));
pq.push(Node(5, 6));
pq.push(Node(1, 9));
pq.push(Node(3, 2));
pq.push(Node(1, 5));
pq.push(Node(4, 0));
// 依次取出元素
while(!pq.empty()){
Node top = pq.top();
cout << top.x << " " << top.y << endl;
pq.pop();
}
return 0;
}
Priority: 1, Name: Task B
Priority: 2, Name: Task D
Priority: 3, Name: Task A
Priority: 4, Name: Task C
Four Application scenario(应用场景）
1. 最短路径算法（Dijkstra算法）
应用场景：
- 问题类型：图论中的单源最短路径问题。
- 示例问题：给定一个带权有向图，计算从起点到所有其他节点的最短路径。
优先队列的作用：
- 在Dijkstra算法中，优先队列用于选择当前未处理节点中距离起点最近的节点，以确保每次扩展的都是最优路径。
上题目：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll find_min_idx(const ll n,vector<ll> &vis,vector<ll> &dis){
ll MINidx=-1,MIN=LLONG_MAX;
for(ll i=0;i<n;i++){
if(dis[i]<MIN&&!vis[i]){
MIN=dis[i];
MINidx=i;
}
}
return MINidx;
}
void Dijkstra(ll idx,const ll n,vector<ll> &vis,vector<ll> &dis,vector<vector<ll>> &mp){
dis[idx]=0;
for(ll i=0;i<n;i++){
ll u=find_min_idx(n,vis,dis);
if(u==-1)break;
vis[u]=1;
for(ll j=0;j<n;j++){
if(!vis[j]&&mp[u][j]>0&&mp[u][j]+dis[u]<dis[j]){
dis[j]=mp[u][j]+dis[u];
}
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string s;cin>>s;
ll n=s.length();
vector<vector<ll>> mp(n,vector<ll>(n,0));
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
cin>>mp[i][j];
}
}
char start;cin>>start;
ll idx=s.find(start);
vector<ll> vis(n,0);
vector<ll> dis(n,LLONG_MAX);
dis[idx]=0;
Dijkstra(idx,n,vis,dis,mp);
for(ll i=0;i<n;i++){
if(i==idx)continue;
cout<<s[i]<<": "<<(dis[i]==LLONG_MAX?0:dis[i])<<endl;
}
return 0;
}2. 最小生成树算法（Prim算法）
应用场景：
- 问题类型：图论中的最小生成树问题。
- 示例问题：给定一个无向带权图，找到包含所有节点且边权和最小的树。
优先队列的作用：
- 在Prim算法中，优先队列用于选择当前可以连接到生成树的最小权重边。
#include<bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
#define int long long
const int N=1e6+10;
vector<pair<int,int>> e[N],g[N];
int n,m;
int vis[N],dis[N],fa[N];
int ans=0,tot=2;
void bfs(){
priority_queue<pair<int,int>> q;
q.push({0,1});
while(q.size()){
auto [d,u] = q.top();
q.pop();
if(vis[u]) continue;
vis[u]=1;
ans+=-d;
for(auto [v,di]:e[u]){
q.push({d-di,v});
}
}
}
void bfs2(){
priority_queue<pair<int,int>> q;
q.push({0,1});
while(q.size()){
auto [d,u] = q.top();
q.pop();
if(vis[u]==tot) continue;
vis[u]=tot;
ans+=-d;
for(auto [v,di]:g[u]){
q.push({d-di,v});
}
}
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,d;
cin>>u>>v>>d;
e[u].push_back({v,d});
g[v].push_back({u,d});
}
bfs();
bfs2();
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T=1;
// cin>>T;
while(T--){
solve();
}
return 0;
}
3. 哈夫曼编码（Huffman Coding）
应用场景：
- 问题类型：数据压缩和编码问题。
- 示例问题：根据字符出现频率构建哈夫曼树，并生成最优前缀编码。
优先队列的作用：
- 哈夫曼编码算法使用优先队列来选择频率最小的两个节点，逐步合并生成哈夫曼树。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node {
ll l, r, p, w, id;
string res;
};
struct Compare {
bool operator()(const Node &a, const Node &b) const {
return a.w != b.w ? a.w > b.w : a.id > b.id;
}
};
void dfs(vector<Node> &nodes, ll id, string code) {
if (nodes[id].l == -1 && nodes[id].r == -1) {
nodes[id].res = code; // 直接赋值哈夫曼编码
return;
}
if (nodes[id].l != -1) dfs(nodes, nodes[id].l, code + "0");
if (nodes[id].r != -1) dfs(nodes, nodes[id].r, code + "1");
}
int main() {
ll n;cin >> n;
string s;cin >> s;
priority_queue<Node, vector<Node>, Compare> pq;
vector<Node> nodes;
for (ll i = 0; i < n; i++) {
ll w;cin >> w;
nodes.push_back({-1, -1, -1, w, i, ""}); // 初始化叶子节点
pq.push(nodes.back());
}
ll nextId = n; // 新生成节点的编号从 n 开始
while (pq.size() > 1) {
Node x = pq.top();pq.pop();
Node y = pq.top();pq.pop();
Node z = {-1, -1, -1, x.w + y.w, nextId++, ""};
z.l = x.id;z.r = y.id;
nodes[x.id].p = z.id;nodes[y.id].p = z.id;
nodes.push_back(z);pq.push(z);
}
ll rootId = pq.top().id;
dfs(nodes, rootId, "");
for (ll i = 0; i < n; i++) cout << nodes[i].res << '\n';
return 0;
}
4. 合并K个有序链表（Merge K Sorted Lists）
应用场景：
- 问题类型：链表操作和归并排序。
- 示例问题：给定K个有序链表，将它们合并为一个有序链表。
优先队列的作用：
- 使用优先队列维护当前K个链表的最小元素，逐步合并。
#include <bits/stdc++.h>
using namespace std;
inline uint64_t read() {
uint64_t x = 0;
char ch = getchar();
while (!isdigit(ch))
ch = getchar();
while (isdigit(ch))
x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x;
}
uint64_t a[10000001], b[10000001];
signed main() {
for (int T = read(), n, m; (T--) && (n = read(), m = read()); ) {
for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i <= m; i++)
b[i] = read();
int j = 1, cnt = 0, ans = 0;
for (int i = 1; i <= n; i++) {
cnt = 0;
while (j <= m && a[i] >= b[j]) {
cnt += (a[i] == b[j]);
j++;
}
ans ^= cnt;
}
printf("%d\n", ans);
}
return 0;
}
5.贪心算法中的应用
应用场景：
- 问题类型：贪心选择性质的问题，如活动安排、区间调度等。
- 示例问题：选择尽可能多的不重叠活动。
优先队列的作用：
- 通过优先队列快速选择最优的下一步操作，如选择最早结束的活动。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,h,n;
struct node{
int a,c,now;
bool operator < (const node &b) const{
return this->now > b.now;
}//冷却完成的时间点越早越优先
}b[200005];
void solve(){
cin >> h >> n;
int turn = 1;
for(int i=1;i<=n;i++) cin >> b[i].a;
for(int i=1;i<=n;i++) cin >> b[i].c;
queue<node> que;
priority_queue<node> pq;
for(int i=1;i<=n;i++) que.push({b[i].a,b[i].c,1});
while(h > 0){
if(!pq.empty()){
turn = pq.top().now;
while(!pq.empty() && pq.top().now == turn){
que.push({pq.top().a,pq.top().c,pq.top().now});
pq.pop();
}
}
while(!que.empty()){
h -= que.front().a;
pq.push({que.front().a,que.front().c,que.front().c+que.front().now});
que.pop();
}
}
cout << turn << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> t;
while(t--){
solve();
}
return 0;
}
6. 动态中位数维护
应用场景：
- 问题类型：动态数据流问题，需要实时获取中位数。
- 示例问题：设计一个数据结构，支持动态插入元素并实时获取中位数。
优先队列的作用：
- 使用两个优先队列（最大堆和最小堆）分别维护较小一半和较大一半的元素，以快速计算中位数。
(写的题目没有涉及过，以后遇到会补充）
7.石子合并问题（Stone Merging Problem）
1. 应用场景
石子合并问题在多种实际应用中具有重要意义，特别是在需要优化合并过程以最小化成本或时间的场景中。通常被归类为**贪心算法（Greedy Algorithms）**问题，因为它涉及在每一步选择最优的局部决策，以期达到全局最优的结果。具体类型包括：
- 最小合并成本：给定一组石子，每次可以合并两个石子，合并成本为这两个石子的重量之和，目标是通过一系列合并操作，使得所有石子最终合并成一个石子，并使得总合并成本最小。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
pq.push(x);
}
ll total_cost = 0;
while (pq.size() > 1) {
int x = pq.top();
pq.pop();
int y = pq.top();
pq.pop();
int merge_cost = x + y;
total_cost += merge_cost;
pq.push(merge_cost);
}
cout << total_cost << endl;
return 0;
}暂时先到这里吧，Good Bye!