priority_queue使用总结

使用方法

最近刚好在补STL的题，顺便来总结一下。

普通的队列是按照进队的先后来决定优先级的，即先进先出。

而优先队列则是按照优先级来排序的，这点与普通的队列不同。

如果你按照大小来决定优先级的话，相同的大小的顺序并不是按照进队的先后来决定的，这里算是之前不知道的知识。

即优先级高的先出。

具体使用

正常的使用，按照大小来决定优先级。

priority_queue<int,vector<int>,greater<int>> q1;//升序
priority_queue<int,vector<int>,less<int>> q2;//降序，默认降序

q1.push(3);q1.push(2);q1.push(1)//1,2,3
q2.push(1);q2.push(2);q2.push(3)//3,2,1

如果是pair类型，则是先比较第一个，再比较第二个。

priority_queue<pair<int, int> > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
// d,c,b

如果需要自定义类型，则需要手写仿函数或者在结构体中重载运算符。

//方法1
struct ty //运算符重载 <
{
    int x;
    ty(int a) {x = a;}
    bool operator<(const tmp1& a) const{
        return x < a.x; //降序
    }
};

//方法2
struct cmp //重写仿函数
{
    bool operator() (ty a, ty b){
        return a.x < b.x; //降序
    }
};
priority_queue<ty> q1;
priority_queue<ty,vector<ty>,cmp> q2;