优先队列

什么是优先队列

优先队列,有着队列的性质,即从尾部插入,在头部取出,由于它的底层是二叉堆,所以它可以在插入元素的时候将其根据优先级进行排列

时间复杂度

由于底层是二叉堆,将元素从堆底推到堆顶时间复杂度为O(logn),故优先队列插入时间复杂度为O(logn)

用法

跟队列唯一不同的地方在于,队列的头部用front来访问,但是优先队列底层是堆,所以用top来访问头部(顶部)

其他用法基本与队列一样

定义

1
2
queue<int> q1;  //队列
priority_queue<int> q2;  //优先队列

自定义优先级

单元素

1
2
3
priority_queue<int> q;  //递增
//等同于
priority_queue<int, vector<int>, less<int>> q;
1
priority_queue<int, vector<int>, greater<int>> q;  //递减

多元素

用结构体存储元素,排序方法跟sort有异曲同工之处

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct book {
    int v1;
    int v2;
    int v3;
    bool operator<(const book& q) const {
        // 想要的优先级规则
        // if (q.v1 == v1) {
        //     if (q.v2 == v2) {
        //         return q.v3 < v3;
        //     }
        //     return q.v2 < v2;
        // }
        // return q.v1 < v1;
    }
};
priority_queue<book> q;