C++中的priority_queue

初始化

priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

pair<int, int>：

• 这是优先队列中存储的元素类型。

vector<pair<int, int>>：

• 这是优先队列内部使用的底层容器类型。

mycomparison：

• 这是自定义的比较函数或比较类，用于定义优先队列的排序规则。

priority_queue 的关键操作

插入元素：push(value)
将元素插入到优先队列中，自动按照优先级进行排序。

访问堆顶元素：top()
返回优先队列中优先级最高的元素（对于最大堆，就是最大元素），但不移除它。

移除堆顶元素：pop()
移除优先队列中优先级最高的元素（最大元素）。

检查队列是否为空：empty()
如果优先队列为空，返回 true，否则返回 false。

获取队列大小：size()
返回优先队列中元素的数量。

自定义比较函数

默认情况下，priority_queue 是一个最大堆（即大元素有更高的优先级），但有时候我们需要最小堆（即小元素有更高的优先级）或者自定义优先级顺序。这可以通过自定义比较函数或仿函数来实现。

最小堆的实现

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // 创建一个最小堆的 priority_queue
    priority_queue<int, vector<int>, greater<int>> pq;

    // 插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);
    pq.push(5);

    // 输出并移除堆顶元素
    while (!pq.empty()) {
        cout << pq.top() << " ";  // 输出堆顶元素
        pq.pop();  // 移除堆顶元素
    }

    return 0;
}

自定义排序
有时我们希望对非基本类型的对象使用 priority_queue，并根据自定义规则排序。例如，我们有一个 pair<int, string>，并且希望根据 pair 的第一个元素（整数）进行最小堆排序。 

#include <iostream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

// 自定义比较函数
struct compare {
    bool operator()(const pair<int, string>& a, const pair<int, string>& b) {
        return a.first > b.first;  // 按照第一个元素（整数）升序排序（最小堆）
    }
};

int main() {
    // 创建一个 priority_queue，按自定义比较函数排序
    priority_queue<pair<int, string>, vector<pair<int, string>>, compare> pq;

    // 插入元素
    pq.push({2, "two"});
    pq.push({1, "one"});
    pq.push({3, "three"});

    // 输出并移除堆顶元素
    while (!pq.empty()) {
        cout << pq.top().first << " " << pq.top().second << endl;
        pq.pop();
    }

    return 0;
}

运行结果

 对自定义函数返回排序解释

在 C++ 的 priority_queue 中，比较函数 operator() 返回 true 时的含义是：

priority_queue 是一个最大堆：默认情况下，它会将优先级最高的元素放在堆顶。
自定义比较函数的返回值：如果比较函数 operator() 返回 true，priority_queue 将认为第一个元素的优先级低于第二个元素。因此，第一个元素将排在第二个元素之后。

如何判断是大顶堆还是小顶堆？
1. 大顶堆（最大堆）：

如果你希望 priority_queue 是一个大顶堆（最大堆），你希望大的元素优先级高，因此需要比较函数在第一个元素比第二个元素小时返回 true。
比较函数：return a < b; （或 a.first < b.first 对于 pair）。
2. 小顶堆（最小堆）：

如果你希望 priority_queue 是一个小顶堆（最小堆），你希望小的元素优先级高，因此需要比较函数在第一个元素比第二个元素大时返回 true。
比较函数：return a > b; （或 a.first > b.first 对于 pair）。

原文地址：https://blog.csdn.net/weixin_74749489/article/details/142795396

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！