C++ STL容器之priority_queue(优先队列)快速入门

可定

发布于 2020-04-20 15:06:11

2.3K0

发布于 2020-04-20 15:06:11

文章被收录于专栏：细嗅蔷薇细嗅蔷薇

priority_queue称为“优先队列”，其底层是用堆实现。

在优先队列中，队首元素一定是当前队列中优先级最高的哪一个。

例如，若在队列中有如下元素且定义好了优先级：

埃罗芒阿（优先级3）
土间埋（优先级2）
公主殿下（优先级5）

那么出队的序列为公主殿下（5）->埃罗芒阿（3）->土间埋（2）。

而且可以在任何时候往优先队列里面加入(push)元素，接着优先队列底层的数据结构堆会随时调整结构，使得每次的队首元素都是优先级最大的。（这里的优先级是可以规定出来的，默认是数字越大优先级越大）

使用priority_queue需于代码头部添加#include，并且随后加上一句：using namespace std;即可。

priority_queue的定义

定义：priority_queue name;

获取堆顶元素

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

与队列不一样的是，优先队列通过top()函数来访问队首元素（堆顶元素）。（队列是通过front()函数和back()函数访问下标）

入队

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

出队

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

检测是否为空

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

获取元素个数

size()：用来获得优先队列中元素的个数，时间复杂度为O(1)

代码：

#include
#include
using namespace std;
int main(){
    priority_queue q;

    //入队
    q.push(3);
    q.push(4);
    q.push(1);

    //通过下标访问元素
    printf("%d\n",q.top());//输出4

    //出队
    q.pop();
    printf("%d\n",q.top());//输出3

    //检测队列是否为空
    if(q.empty() == true) {
        printf("Empty\n");
    } else {
        printf("Not Empty\n");
    }

    //获取长度
    //printf("%d\n",q.size());//输出3
}

优先队列内元素优先级的设置

常见用途

需要建立字符或字符串与整数之间映射的题目

判断大整数或者其他类型数据是否存在的问题，可以把map当成bool数组用

字符串和字符串的映射也有可能会用到

延伸

（1)如果一个键需要对应多个值，只能使用multimap而不能使用map。

（2）C++11标准还增加了unordered_map，以散列替代map内部的红黑树实现，使其可以用来处理值只映射而不按key排序的需求，速度比map快很多。

优先队列内元素优先级的设置

如何定义优先队列内元素的优先级是运用好优先队列的关键。

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

一般情况下，数字大的优先级更高。（char类型的为字典序最大）

对于基本结构的优先级设置。下面两种优先队列的定义是等价的：

priority_queue<int> q;

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

第二种定义方式中的括号里：

第二个参数填写的是成在底层数据结构堆(heap)的容器；若第一个参数为double或char，则只需要填写vector<double>或vector<char>。
第三个参数是对一个参数的比较类； less<int>表示数字大的优先级越大，而greater<int>则反之`

举个例子：

如果想让优先队列总是把最小的元素放在队首，需进行以下定义：priority_queue<int, vector<int>, grater<int>> q;

结构体的优先级设置

举个例子：

下面是关于动漫人物的结构体 struct comic_character{ string name; int bust; }; 现在希望按动漫人物胸围大的为优先级高，就需要使用重载(overload)运算符小于"<"。而重载是指对已有运算符进行重新定义，即把改变其功能将其重载为大于号的功能。

以下为其写法：

struct comic_character{
    string name;
    int bust;
    friend bool operator < (comic_character c1, comic_character c2){
        return c1.bust < c2.bust;
    }
};

其中，结构体中增加了一个函数。

"friend"为友元。

后面一大串是对comic_character类型的操作符“<”进行了重载。此处重载后小于号还是小于号的作用。

提示：重载大于号会编译错误（一般来说只需要重载小于号，即c1>c2等价于c2<c1，c1==c2等价于判断!(c1<c2)&&!(c2<c1)）

若想要以胸围小的动漫人物为优先级高，那么只需要把return中的小于改为大于号即可，此处不再赘述。

重大发现：重载与sort函数的比较。

这里对小于号的重载与排序函数sort中cmp函数有点类似。它们的参数和函数内部看似都是一样的。

虽然这两者的作用是类似的，但是效果看上去似乎的“相反”的。

在sort中，如果是"return c1.bust > c2.price"，那么则是按胸围从大到小排序。

而在优先队列的重载中却是把胸围小的放到队首。

总之《优先队列的重载与sort中的cmp函数的效果是相反的。

另外

怎么把重载放在结构体外面（正如sort中的cmp函数）呢？

只要把friend去掉，把小于号改成一对小括号，然后把重载的函数写在结构体外面，同时将其struct包装起来。

即：

struct comic_character{
    string name;
    int bust;
};
struct cmp{
    bool operator () (comic_character c1, comic_character c2){
        return c1.bust > c2.bust;
    }
};
int main(){
    priority_queue<comic_character, vector<comic_character>, cmp> q;
    ......
}

小提示

（1）即使是基本数据类型或者其他STL容器（如set），也可通过“另外”部分的方式来定义优先级。

（小作业：想想怎么定义？）

（2）使用top()函数前，必须使用empty()判断优先队列是否为空。

题外话

如果结构体内的数据较为庞大（如字符串或数组），建议使用引用来提高效率，在比较类的参数中加上"const"和"&"。

即:

在结构体内： friend bool operator < (const comic_character &c1, const comic_character &c2){ return c1.bust > c2.bust; } 或在结构体外： bool operator () (const comic_character &c1, const comic_character &c2){ return c1.bust > c2.bust; }

常见用途

（1）可以解决一些贪心问题

（2）也可以对Dijkstra算法进行优化

优先队列的本质是堆

本文标题：《C++ STL容器之priority_queue(优先队列)快速入门》

本文链接：https://cloud.tencent.com/developer/article/1616910

特别声明：除特别标注，本站文章均为原创，本站文章原则上禁止转载，如确实要转载，请电联：wangyeuuu@qq.com，尊重他人劳动成果，谢过~

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-02-15，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

c++

登录后参与评论

0 条评论

热度