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(){// 使用 structPointStruct ps;ps.x = 10; // 可以直接访问和修改ps.y = 20;cout << "PointStruct: (" << ps.x << ", " << ps.y << ")\n";// 使用 classPointClass 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!