基础用法
int main() {
/*
c++优先队列默认为大根堆
*/
priority_queue<int, vector<int>> heap;
heap.push(1);
heap.push(2);
heap.push(3);
while(heap.size()){
cout<<heap.top()<<' ';
heap.pop();
}
/*output: 3 2 1*/
/*
优先队列设置为小根堆
*/
priority_queue<int, vector<int>, greater<int>> heap1;
heap1.push(1);
heap1.push(2);
heap1.push(3);
while(heap1.size()){
cout<<heap1.top()<<' ';
heap1.pop();
}
/*output: 1 2 3*/
return 0;
}
利用仿函数自定义优先级比较
struct comparsion{
bool operator () (PII A, PII B){
if(A.first==B.first) return A.second>B.second;
return A.first<B.first;
}
};
int main(){
/*
自定义优先级进行比较
typedef pair<int,int> PII;
按照first从小到大排序,first相等时,按照second从大到小排序
*/
priority_queue<PII, vector<PII>, comparsion> heap;
heap.push({2,3});
heap.push({1,4});
heap.push({2,1});
heap.push({1,10});
while(heap.size()){
auto t= heap.top();
heap.pop();
cout<<t.first<<' '<<t.second<<endl;
}
/*
与我们需要的刚好相反
2 1
2 3
1 4
1 10
*/
return 0;
}
修改自定义比较符号
struct comparsion{
bool operator () (PII A, PII B){
if(A.first==B.first) return -A.second>-B.second;
return -A.first<-B.first;
}
};
int main(){
/*
自定义优先级进行比较
typedef pair<int,int> PII;
按照first从小到大排序,first相等时,按照second从大到小排序
*/
priority_queue<PII, vector<PII>, comparsion> heap;
heap.push({2,3});
heap.push({1,4});
heap.push({2,1});
heap.push({1,10});
while(heap.size()){
auto t= heap.top();
heap.pop();
cout<<t.first<<' '<<t.second<<endl;
}
/*
2 1
2 3
1 4
1 10
*/
return 0;
}
标签:PII,优先,队列,heap1,second,heap,push,模板,first
From: https://www.cnblogs.com/Biang-blog/p/18393945