C++优先队列stl
2018-11-16 / Luo Jinrong   

早上本来想写写英语作文的，结果看作文题目过于简短，于是就来学学优先队列的用法哈哈哈。

优先队列介绍

队列是一种先进先出的数据结构，比较符合我们的思维模式，至今我也学了一些算法使用了队列，比如最短路径的SPFA算法，现在又学到了拓扑排序。但是这次并不是队列这么简单，而是用到的高级版的队列，即优先队列。

优先队列(priority queue)，顾名思义，就是队列中的各元素被赋予了相应的优先级，就好像最原始的队列，其实也是有优先级的，即是先入队的优先。而优先队列，其元素的优先级就不仅仅局限于入队的先后顺序，而是可以被自定义为元素的大小，这类似与堆的操作。

C++的标准模板库(STL)中的优先队列

在STL中定义的优先队列，其元素的默认比较规则是按元素从大到小排列，我们可以通过重载”<”来重新定义比较规则。(据说重载”>”会出问题，具体以后在尝试，flag先立着)。

接下来我们来看看优先队列在STL中是如何被定义的：priority_queue<Type,Container,Functional>，其中Type是数据类型（可以是任何数据类型，包括自己定义的一些乱七八糟的），Container是存储数据所使用的容器（可以使用vector、deque，但是不能使用list，默认是vector），Functional是比较的方式。

STL优先队列的使用

定义

priority_queue<Type,Container=vector<Type>,cmp=greater<Type>>que;

其中，第一个参数为数据类型，第二个参数为容器（默认为vector），第三个参数为比较函数（默认大值优先）。

比较函数的写法

  • 使用C++自带的库函数
  • 自定义优先级1
  • 自定义优先级2
  • 自定义优先级3

方法一：使用C++自带的库函数

首先在头文件中引用include库函数

#include<functional>

functional 中提供了如下的基于模板的比较函数对象。

  • equal_to: 等于
  • not_equal_to: 不等于
  • greater: 大于
  • greater_equal: 大于等于
  • less: 小于
  • less_equal: 小于等于

创建方法：priority_queue<int,vector<int>,less<int>>que;

方法二：自定义优先级1，队列元素为数值型

1
2
3
4
5
6
7
8
9
10
struct cmp1{
    bool operator()(int &a,int &b){
        return a<b;//最大值优先
    }
};
struct cmp{
    bool operator()(int &a,int &b){
        return a<b;//最小值优先
    }
};

创建方法：priority_queue<int,vector<int>,cmp1>que;

方法三：自定义优先级2，队列元素为结构体

1
2
3
4
5
6
7
8
9
10
11
12
struct node1{
    int x,y;
    bool operator < (const node1 &a) const {//只能重载<
        retrun x<a.x;//最大值优先
    }
};
struct node2{
    int x,y;
    bool operator < (const node2 &a) const {
        retrun x>a.x;//最小值优先
    }
};

创建方法：priority_queue<node1>que;

方法四：自定义优先级3，队列元素为结构体

1
2
3
4
5
6
7
8
9
struct node{
    int x,y;
}；
bool operator < (const node &a,const node &b){
    return a.x<b.x;按成员x最大值优先
}
/*bool operator < (const node &a,const node &b){//由于都是重载<,所以两种比较形式只能同时存在一种
    return a.y>b.y;按成员y最小值优先
}*/

创建方法：priority_queue<node>que;

return 0;

本文链接：
https://luojinrong.github.io/2018/11/16/C-优先队列stl/