C++中的优先级队列按第一和第二元素排序
优先级队列:优先级队列是队列的扩展,其中与优先级相关联的元素和具有较高优先级的元素首先弹出。优先级队列可以包含具有各种数据类型的元素,例如整数、整数对、自定义数据类型。但有一件事是共同的,即有一个元素定义了元素的优先级。因此,一对元素的优先级队列可以有两种类型的排序-
- 按对的第一个元素排序
- 按对的第二个元素排序
按第一个元素排序的优先级队列(Max)
如果元素以一对的形式呈现,则在C++中,元素的优先级默认取决于第一个元素。因此,我们只需要使用一对元素的优先级队列即可。
// 优先级队列的C++实现
// 按第一个元素排序
#include <iostream>
#include <queue>
using namespace std;
// 按照第一个元素打印数据的函数
void showpq(
priority_queue<pair<int,int> > g)
{
// 循环打印元素
// 直到优先级队列为空
while (!g.empty()) {
cout << g.top().first
<< " " << g.top().second
<< endl;
g.pop();
}
cout << endl;
}
// 主函数
int main()
{
priority_queue<pair<int,int> > p1;
// 插入元素
p1.push(make_pair(4, 5));
p1.push(make_pair(5, 4));
p1.push(make_pair(1, 6));
p1.push(make_pair(7, 3));
p1.push(make_pair(9, 4));
showpq(p1);
return 0;
}
输出:
9 4
7 3
5 4
4 5
1 6
注意: 如果一些对的第一个元素相同,则将基于第二个元素进行比较。
按第一个元素排序的优先级队列(min)
如果元素以一对的形式呈现,则在C++中,元素的优先级默认取决于第一个元素。默认情况下,优先级队列是最大堆。因此,我们只需要使用带有greater<>函数对象的元素对的优先级队列即可。
// 优先级队列的C++实现
// 按第一个元素排序(min)
#include <iostream>
#include <queue>
using namespace std;
// 按照第一个元素打印数据的函数
void showpq(priority_queue<pair<int,int> , vector<pair<int,int>>, greater<pair<int,int>> > g)
{
// 循环打印元素
// 直到优先级队列为空
while (!g.empty()) {
cout << g.top().first
<< " " << g.top().second
<< endl;
g.pop();
}
cout<< endl;
}
// 主函数
int main()
{
// 最小堆
priority_queue<pair<int,int> , vector<pair<int,int>>, greater<pair<int,int>> > p1;
// 插入元素
p1.push(make_pair(4, 5));
p1.push(make_pair(5, 4));
p1.push(make_pair(1, 6));
p1.push(make_pair(7, 3));
p1.push(make_pair(9, 4));
showpq(p1);
return 0;
}
按第二个元素排序的优先级队列(Max)
思路是使用具有运算符重载概念的结构来对优先级队列进行排序,以其第二个元素作为排序依据。下面是按第二个元素排序的优先级队列的实现-
// C++实现按第二个元素排序的优先队列
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pd;
// 结构体用于排序(按第二个元素的大小)
struct myComp {
constexpr bool operator()(
pair<int, int> const& a,
pair<int, int> const& b)
const noexcept
{
return a.second < b.second;
}
};
// 显示优先队列中的元素
void showpq(
priority_queue<pd,
vector<pd>, myComp>
g)
{
// 循环打印元素,直到优先队列为空
while (!g.empty()) {
cout << g.top().first
<< " " << g.top().second
<< endl;
g.pop();
}
cout << endl;
}
// 主函数
int main()
{
priority_queue<pd, vector<pd>, myComp> p1;
p1.push(make_pair(4, 5));
p1.push(make_pair(5, 4));
p1.push(make_pair(1, 6));
p1.push(make_pair(7, 3));
p1.push(make_pair(9, 4));
// 调用函数
showpq(p1);
return 0;
}
输出:
1 6
4 5
9 4
5 4
7 3
以第二个元素排序的优先队列(最小值)
利用运算符重载来实现按第二个元素排序的优先队列,最小元素位于顶部。下面是实现代码:
// C++实现按第二个元素排序的优先
// 队列(按第二个元素的大小)
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pd;
// 结构体用于重载运算符(按第二个元素的大小)
struct myComp {
constexpr bool operator()(
pair<int, int> const& a,
pair<int, int> const& b)
const noexcept
{
return a.second > b.second;
}
};
// 显示优先队列中的元素
void showpq(
priority_queue<pd, vector<pd>, myComp> g)
{
// 循环打印元素
while (!g.empty()) {
cout << g.top().first
<< " " << g.top().second
<< endl;
g.pop();
}
cout << endl;
}
// 主函数
int main()
{
priority_queue<pd, vector<pd>, myComp> p1;
// 插入元素
p1.push(make_pair(4, 5));
p1.push(make_pair(5, 4));
p1.push(make_pair(1, 6));
p1.push(make_pair(7, 3));
p1.push(make_pair(9, 4));
showpq(p1);
return 0;
}
输出:
7 3
5 4
9 4
4 5
1 6