数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的配对优先级队列（按第一项排序）
优先级队列是一种抽象数据类型，用于存储一组具有优先级的元素的集合，它支持根据元素的优先级插入和删除元素，也就是说，可以随时删除具有最高优先级的元素。优先级队列不会像栈、队列、列表等那样按照其位置线性存储元素。优先级队列 ADT（抽象数据类型）根据元素的优先级存储元素。
优先级队列支持以下函数：
Size() - 用于计算优先级队列的大小，因为它返回其中的元素数量。
Empty() - 如果优先级队列为空，则返回 true，否则返回 false
Insert(element) - 用于将新元素插入优先级队列
Min() - 返回具有最小关联键值的元素，如果优先级队列为空，则显示错误消息。
removeMin() - 删除 min() 函数引用的元素。
任务是在 C++ 中实现配对优先级队列的概念，并按第一项排序。
我们可以用类似于堆的方式解决问题，有两种方法可以解决问题
- 最大优先级或最大堆
- 最小优先级或最小堆
堆是一种树形结构，其中节点以特定顺序排列。堆有两种类型：最小堆和最大堆。在最小堆中，根节点或父节点小于其子节点，而在最大堆中，根节点或父节点大于其子节点。
示例
Input: priorityq.push(make_pair(18, 200)) Input: priorityq.push(make_pair(18, 200)) priorityq.push(make_pair(29, 100)) priorityq.push(make_pair(11, 400)) Output: 29 100 Input: priorityq.push(make_pair(10, 200)) priorityq.push(make_pair(20, 100)) priorityq.push(make_pair(19, 400)) Output: 20 100 Through Max priority (Max heap)
算法
Start Step 1-> In main function() Define priority_queue<pair<int, int> > priorityq Call priorityq.push(make_pair(18, 200)) Call priorityq.push(make_pair(29, 100)) Call priorityq.push(make_pair(11, 400)) Set pair<int, int> top = priorityq.top() Print top.first and top.second Stop
示例
#include <bits/stdc++.h>
using namespace std;
// main program
int main() {
priority_queue<pair<int, int> > priorityq;
priorityq.push(make_pair(18, 200));
priorityq.push(make_pair(29, 100));
priorityq.push(make_pair(11, 400));
pair<int, int> top = priorityq.top();
cout << top.first << " " << top.second;
return 0;
}输出
29 100
通过最小优先级（最小堆）
算法
Start Step 1-> In main function() Define priority_queue<pair<int, int> > priorityq Call pq.push(make_pair(10, 200)) Call pq.push(make_pair(20, 100)) Call pq.push(make_pair(15, 400)) Set pair<int, int> top = pq.top() Print top.first and top.second Stop
示例
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
// main program
int main() {
priority_queue<pi, vector<pi>, greater<pi> > pq;
pq.push(make_pair(10, 200));
pq.push(make_pair(20, 100));
pq.push(make_pair(15, 400));
pair<int, int> top = pq.top();
cout << top.first << " " << top.second;
return 0;
}输出
10 200
更新于： 2019年12月23日
3K+ 浏览量
广告