做没有好的网站你懂的,房产网站制作模板,全国城乡和住房建设厅查询网,自己服务器可以做网站priority_queue比较规则
std::priority_queue实际上就是一个堆#xff0c;可用于堆排序。
std::priority_queue是C STL中的一个容器适配器#xff0c;它提供常数时间查找最大元素的功能。默认情况下#xff0c;它使用元素的运算符进行排序#xff08;升序#xff09…priority_queue比较规则
std::priority_queue实际上就是一个堆可用于堆排序。
std::priority_queue是C STL中的一个容器适配器它提供常数时间查找最大元素的功能。默认情况下它使用元素的运算符进行排序升序所以最大的元素总是位于队列的顶部。然后如果你想自定义排序规则你需要提供自己的比较函数可以通过在定义std::priority_queue时传入一个比较函数对象来实现。
默认情况下标准库在元素类型上使用运算符来确定相对优先级priority_queue中默认less建大根堆在自定义类型时会调用operator,若返回true,说明此此元素的父节点小于此节点需要向上调整。所以priority_queue默认使用时而又想建小堆要重载operator需要return a.xb.x方可。
比较函数对象
让priority_queue按照元素的相反顺序排序我们传递了std::greaterint作为比较函数对象给std::priority_queue这使得队列以相反的顺序排序即最小的元素总是在队列的顶部。
#include queue
#include vector
#include functionalint main() {// 使用greaterint作为比较函数对象创建优先队列使队列按照元素的相反顺序排序std::priority_queueint, std::vectorint, std::greaterint pq; // 小根堆// greaterpairint,int // lesspairint,int// 向队列添加元素pq.push(3);pq.push(5);pq.push(1);// 打印并移除队列顶部的元素由于比较函数对象为greaterint因此打印的顺序为135while(!pq.empty()) {std::cout pq.top() ;pq.pop();}return 0;
}自定义函数比较对象
在C中priority_queue的默认行为是生成大根堆。如果想要生成小根堆可以使用构造函数的第三个参数传入一个自定义的比较函数。对于类型为pairint, pairint,int的小根堆可以定义一个比较函数如下
struct cmp {bool operator() (pairint, pairint,int a, pairint, pairint,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的时候使用这个比较函数
//我们定义了一个小根堆堆的元素是pairint, pairint,int类型的使用自定义的比较函数cmp对元素进行排序。
priority_queuepairint, pairint,int, vectorpairint, pairint,int, cmp pq;
// 当然也可以使用lambda重载运算符
需要注意的是当使用重载运算符定义排序规则时我们必须保证对所有可能的元素组合具有对称性和传递性以确保排序规则的正确性也就是说自定义比较时不能出现 或 这样破坏严格弱排序的定义规则。
#include queue
#include iostreamclass MyClass {
public:int value;MyClass(int val) : value(val) {}// 重载小于运算符bool operator(const MyClass other) const {return this-value other.value; // 注意我们实际定义的是大于}
};int main() {std::priority_queueMyClass 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;
}
