STL大法好
STL优先队列就是一个封装的堆，学会熟练运用，免去手写堆的麻烦 其实是不会自己写
格式：priority_queue< 类型 , vector<类型> , 比较类 > q;
优先队列的源码比较奇特，别的容器默认从小到大排序，但是 priority_queue<> 默认是大根堆的，这是因为 优先队列队首指向最后，队尾指向最前面的缘故！ 每次入队元素进去经排序调整后，优先级最大的元素排在最前面，也就是队尾指向的位置，这时候队首指向优先级最小的元素！所以我们重载运算符的时候比较类里面写>就相当于<排序方式，这点需要花点时间想想
举个例子：
int类型：
//在写比较类时可以用重载运算符的方法
//要注意的是STL优先队列默认的运算符是括号，即 ()
struct cmp{
bool operator () (int a,int b){//通过结构体来重载运算符
return a<b;//虽然 reture a<b 但堆顶是最大的
}
};
struct cmp2{
bool operator () (int a,int b){
return a>b;//虽然 reture a>b 但堆顶是最小的
}
};
priority_queue<int,vector<int>, cmp> q;//大顶堆
priority_queue<int,vector<int>, cmp2> q2;//小顶堆
我们插入以下几个数：
1 , 5 , 7 , 3 , 2
q.push(1);q2.push(1);
q.push(5);q2.push(5);
q.push(7);q2.push(7);
q.push(3);q2.push(3);
q.push(2);q2.push(2);
puts("q:");
while(q.size()){
int h=q.top();
q.pop();
cout<<h<<" ";
}
puts("\nq2:");
while(q2.size()){
int h=q2.top();
q2.pop();
cout<<h<<" ";
}
输出结果:
结构体类型：
//在写比较类时可以用重载运算符的方法
//要注意的是STL优先队列默认的运算符是括号，即 ()
struct node{
int x,y;
node(int _x,int _y){x=_x,y=_y;}
};
struct cmp{
bool operator () (node a,node b){//通过cmp结构体来重载运算符
return a.x<b.x;
}
};
struct cmp2{
bool operator () (node a,node b){
return a.y>b.y;
}
};
priority_queue<node,vector<node>, cmp> q;//按x降序堆
priority_queue<node,vector<node>, cmp2> q2;//按y升序堆
我们插入：
{1,2} {4,5} {3,7} {2,1} {5,3}
q.push(node(1,2));q2.push(node(1,2));
q.push(node(4,5));q2.push(node(4,5));
q.push(node(3,7));q2.push(node(3,7));
q.push(node(2,1));q2.push(node(2,1));
q.push(node(5,3));q2.push(node(5,3));
puts("q:");
while(q.size()){
node h=q.top();
q.pop();
cout<<h.x<<" "<<h.y<<"\n";
}
puts("\nq2:");
while(q2.size()){
node h=q2.top();
q2.pop();
cout<<h.x<<" "<<h.y<<"\n";
}
输出结果:
