在priority_queue内部排序

Question

我的priority_queue是向后排序的,我不明白为什么.这是来自cplusplus.com

表达式comp(a,b),其中comp是这种类型的对象,a和b是容器中的元素,如果a被认为在函数定义的严格弱排序中的b之前,则返回true.

现在在我的Comparator的类operator()函数中,如果a小于b,则a应该在b之前.因此,如果a小于b,则返回true.但最后我得到序列"321",但我反而选择了"123"!

#include <iostream>
#include <queue>
using namespace std;

class Number{
    int x;
public:
    Number(int _x):x(_x){}
    int getX()const{return x;}
};

class Comparator{
public:
    bool operator()(const Number& a,const Number& b){
        if (a.getX()<b.getX()){
            return true;
        } else {
            return false;
        }
    }
};

int main(){
    priority_queue<Number,vector<Number>,Comparator> pq;
    pq.push(2);
    pq.push(1);
    pq.push(3);

    while (!pq.empty()){
        cout<<pq.top().getX();
        pq.pop();
    }

    return 0;
}

Answer 1

该网站还说:

根据这种严格的弱排序,弹出的元素是最后一个

因此元素以弱排序的相反顺序弹出.这是因为priority_queue实现了最大堆,即首先弹出最大元素(由弱排序定义)的堆.

如果你想实现一个min-heap(一个会将元素从最小值弹出到最大值),你需要让你的比较函数做相反的操作,即true当且仅当a > b根据你的顺序返回时才返回.