STL常用模板：PriorityQueue优先队列

概念

C++优先队列类似队列，具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的,使优先级高的排在前面，优先出列。

头文件

1	#include <queue>

名字空间

std

构造函数

定义:

1	priority_queue<Type, Container, Functional>

Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

基本类型构造:
如果我们把后面俩个参数缺省的话，优先队列就是大根堆，队头元素最大。

//大根堆，降序队列
priority_queue<int> Q1;
priority_queue <int,vector<int>,less<int> > Q2;

// 小根堆，升序队列                           ↓这里一定要有空格，不然成了右移运算符
priority_queue<int, vector<int>, greater<int> > Q3;

greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

结构体构造:


//方法1
struct tmp1{

  //你要用的数据
  int val;

  //初始化函数，方便构造
  tmp1(int v):val(v){};

  //重载'<'运算符（且只能重载'<'），根据自己的需求进行排序，最终实现优先级从高到低的排序
  bool operator < (const tmp1 &rhs) const {
        return val < rhs.val;//返回true则表示this优先级比rhs低，往后排，false反之
    } 
}

//方法2
struct tmp2{ //重写仿函数
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

...

priority_queue<tmp1> Q1;
priority_queue<tmp1, vector<tmp1>, tmp2> Q2;

常用函数

empty

语法:

1	bool empty();

empty()函数返回真(true)如果优先队列为空，否则返回假(false)。

pop

语法:

1	void pop();

pop()函数删除优先队列中的第一个元素。

push

语法:

1	void push( const TYPE &val );

push()函数添加一个元素到优先队列中，值为val。

size

语法:

1	size_type size();

size()函数返回优先队列中存储的元素个数。

top

语法:

1	TYPE &top();

top()返回一个引用，指向优先队列中有最高优先级的元素。注意只有pop()函数删除一个元素。

参考资料

c++优先队列(priority_queue)用法详解