priority_queue比较规则

priority_queue比较规则

std::priority_queue实际上就是一个堆，可用于堆排序。

std::priority_queue是C++ STL中的一个容器适配器，它提供常数时间查找最大元素的功能。默认情况下，它使用元素的<运算符进行排序（升序），所以最大的元素总是位于队列的顶部。然后，如果你想自定义排序规则，你需要提供自己的比较函数，可以通过在定义std::priority_queue时传入一个比较函数对象来实现。

默认情况下，标准库在元素类型上使用<运算符来确定相对优先级，priority_queue中，默认less<>建大根堆，在自定义类型时，会调用operator<,若返回true,说明此此元素的父节点小于此节点，需要向上调整。所以priority_queue默认使用时，而又想建小堆，要重载operator<，需要return a.x>b.x，方可。

比较函数对象

让priority_queue按照元素的相反顺序排序，我们传递了std::greater<int>作为比较函数对象给std::priority_queue，这使得队列以相反的顺序排序，即最小的元素总是在队列的顶部。

#include <queue>
#include <vector>
#include <functional>

int main() {
    // 使用greater<int>作为比较函数对象创建优先队列，使队列按照元素的相反顺序排序
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;		// 小根堆
    // greater<pair<int,int>>	
    // less<pair<int,int>>
    
    
    // 向队列添加元素
    pq.push(3);
    pq.push(5);
    pq.push(1);

    // 打印并移除队列顶部的元素，由于比较函数对象为greater<int>，因此打印的顺序为1，3，5
    while(!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

自定义函数比较对象

在C++中，priority_queue的默认行为是生成大根堆。如果想要生成小根堆，可以使用构造函数的第三个参数，传入一个自定义的比较函数。对于类型为pair<int, pair<int,int>>的小根堆，可以定义一个比较函数如下：

struct cmp {
    bool operator() (pair<int, pair<int,int>> a, pair<int, pair<int,int>> b) {
        if(a.first > b.first) {
            return true;
        } else if(a.first == b.first) {
            if(a.second.first > b.second.first) {
                return true;
            } else if(a.second.first == b.second.first && a.second.second > b.second.second) {
                return true;
            }
        }
        return false;
    }
};

然后在定义priority_queue的时候使用这个比较函数：

//我们定义了一个小根堆，堆的元素是pair<int, pair<int,int>>类型的，使用自定义的比较函数cmp对元素进行排序。
priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, cmp> pq;
// 当然也可以使用lambda

重载运算符

需要注意的是，当使用重载运算符定义排序规则时，我们必须保证对所有可能的元素组合具有对称性和传递性，以确保排序规则的正确性，也就是说自定义比较时不能出现<= 或 >=这样破坏严格弱排序的定义规则。

#include <queue>
#include <iostream>

class MyClass {
public:
   int value;
   MyClass(int val) : value(val) {}

   // 重载小于运算符
   bool operator<(const MyClass& other) const {
       return this->value > other.value;  // 注意我们实际定义的是大于
   }
};

int main() {
    std::priority_queue<MyClass> pq;

    pq.push(MyClass(3));
    pq.push(MyClass(5));
    pq.push(MyClass(1));

    while (!pq.empty()) {
        std::cout << pq.top().value << " ";
        pq.pop();
    }

    return 0;
}