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;
}

输出:

注意： 如果一些对的第一个元素相同，则将基于第二个元素进行比较。

按第一个元素排序的优先级队列(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;
}

输出：

以第二个元素排序的优先队列（最小值）

利用运算符重载来实现按第二个元素排序的优先队列，最小元素位于顶部。下面是实现代码：

// 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;
}