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

发布于 2020-02-15  131 次阅读


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://wnag.com.cn/816.html

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


正因为有要好好实现的梦想,所以今天也要好好加油。