跳到主要内容

priority_queue

就是堆。 但无法任意删除一个数。

它与queue的操作类似，不同之处在于：每次增加/删除元素之后，它将对元素位置进行调整，使得头部元素总是最大的。也就是说，每次删除操作总是把最大（优先级最高）的元素去掉。

在头文件queue中定义，可基于deque和vector来实现。

头文件 #include <queue>。 声明 priority_queue< typename > name;

和队列不一样的是，优先队列没有 front() 函数与 back() 函数，而只能通过 top() 函数来访问队首元素（也可以称为堆顶元素），也就是优先级最高的元素。

示例如下：

#include <stdio.h>
#include <queue>
using namespace std;
int main()
{
    priority_queue<int> q;
    q.push(3);
    q.push(4);
    q.push(1);
    printf("%d\n",q.top());
    return 0;
}
output
4

常用函数​

push()​

push(x) 将令 x 入队，时间复杂度为 O(logN)，其中 N 为当前优先队列中的元素个数。

top()​

top() 可以获得队首元素（即堆顶元素），时间复杂度为 O(1) 。

pop()​

pop() 令队首元素（即堆顶元素）出队，时间复杂度为 O(logN)，其中 N 为当前优先队列中的元素个数。

#include <stdio.h>
#include <queue>
using namespace std;
int main()
{
    priority_queue<int> q;
    q.push(3);
    q.push(4);
    q.push(1);
    printf("%d\n",q.top());
    q.pop();
    printf("%d\n",q.top());
    return 0;
}
output
4
3

empty()​

empty() 检测优先队列是否为空，返回 true 则空，返回 false 则非空。时间复杂度为 O(1)。

size()​

size() 返回优先队列内元素的个数，时间复杂度为 O(1)。

priority queue 内元素优先级的设置​

如何定义优先队列内元素的优先级是运用好优先队列的关键，下面分别介绍基本数据类型（例如 int、double、char）与结构体类型的优先级设置方法。

基本数据类型的优先级设置​

此处指的基本数据类型就是 int 型、double 型、char 型等可以直接使用的数据类型，优先队列对它们的优先级设置一般是大顶堆，因此队首元素就是优先队列内元素最大的那个（如果 char 型，则是字典序最大的）。

对基本数据类型来说，下面两种优先队列的定义是等价的：

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

可以发现，第二种定义方式的尖括号内多出了两个参数：

一个是 vector<int>，另一个是 less<int>。

其中 vector<int>（也就是第二个参数）填写的是来承载底层数据结构堆（heap）的容器，如果第一个参数是 double 型或 char 型，则此处只需要填写 vector<double> 或 vector<char>；

而第三个参数 less<int> 则是对第一个参数的比较类，less<int> 表示数字大的优先级越大，而 greater<int> 表示数字小的优先级越大。

因此，如果想让优先队列总是把最小的元素放在队首，只需进行如下定义：

priority_queue<int,vector<int>,greater<int>> q;
怎么记

greater表示大多数都比那一个大, 所以是小顶堆

自定义

struct cmp
{ //这个比较要用结构体表示
    bool operator()(int &a, int &b) const
    {
        return a > b;
    }
};

priority_queue<int,vector<int>,cmp> q;    //使用自定义比较方法
priority_queue<int> pq;
Loading Comments...