优先队列的两种自定义排序方式

时间：2025-04-04 08:11:47

首先简单的优先队列的定义方法有三种

1.默认从大到小排序

priority_queue<int>q;

2.等价于上面（从大到小排序）

priority_queue<int,vector<int>,less<int> >q;//注意这里最后的两个>要分开

3.定义从小到大排序的优先队列

priority_queue<int,vector<int>,greater<int> >q;

定义包含结构体的多级优先队列

1.定义在结构体内的友元函数方法

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long int LL;
const int MAXN(1e5);
struct node {
    int x,y;
    friend bool operator <(node p,node q) {
        return >; // >号代表从小到大排序 （按照x排序）
    }
}nod;
priority_queue<node>q;
int main() {
    (node{2,3});
    (node{1,5});
    (node{5,4});
    while(!()) {
        cout<<().x<<" "<<().y<<endl;
        ();
    }
}

 

 

2.定义在结构体外，自定义排序函数

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long int LL;
const int MAXN(1e5);
struct node {
    int x,y;
}nod;
struct cmp {
    bool operator() (const node &p,const node &q) {
        return >;// >号代表从小到大排序
    }
};
priority_queue<node,vector<node>,cmp>q;
int main() {
    (node{2,3});
    (node{1,5});
    (node{5,4});
    while(!()) {
        cout<<().x<<" "<<().y<<endl;
        ();
    }
}

注意的地方

优先队列和普通队列有两点不同:

第一是获得队首元素的写法是()，普通队列是()

第二是写代码的过程中踩过的坑：

在上述自定义结构体排序中，如果是普通队列套结构体，可以利用以下写法对结构体内的队首元素进行修改

().x=v;

但是在优先队列里不能这样进行修改。

（虽然是个小问题，但是在有的代码中，优先队列不能这样直接修改元素会增加代码的编写难度，个人认为）

相关文章