目录
1. 优先级队列（priority_queue）
1.1 基本概念
1.2 优先级队列的定义
1.3 通过重写仿函数来支持自定义数据类型
1.4 通过运算符重载来支持自定义比较函数
1.5 优先级队列的基本操作
2. 示例程序
之前已经提到了队列（queue），队列是一种先进先出（First in First out，FIFO）的数据类型。每次元素的入队都只能添加到队列尾部，出队时从队列头部开始出。
优先级队列（priority_queue）其实，不满足先进先出的条件，更像是数据类型中的“堆”。优先级队列每次出队的元素是队列中优先级最高的那个元素，而不是队首的元素。这个优先级可以通过元素的大小等进行定义。比如定义元素越大优先级越高，那么每次出队，都是将当前队列中最大的那个元素出队。个人感觉这就是所谓“优先级”的定义。
现在看优先级队列是不是就是“堆”了，如果最大的元素优先级最高，那么每次出队的就是当前队列中最大的元素，那么队列实际就相当于一个大顶堆，每次将堆根节点元素弹出，重新维护大顶堆，就可以实现一个优先级队列。
C++中，使用优先级队列需要包含头文件<queue>，优先级队列的定义如下：
priority_queue<typename, container, functional>定义一个优先级队列的示例如下：
//构造一个大顶堆，堆中小于当前节点的元素需要下沉，因此使用less
priority_queue<int, vector<int>, less<int>> priQueMaxFirst;
//构造一个小顶堆，堆中大于当前节点的元素需要下沉，因此使用greater
priority_queue<string, vector<string>, greater<string>> priQueMinFirst;仿函数是通过重载“()”运算符来模拟函数操作的类。
先自定义一个类Data，将id作为该类的关键字，进行比较，重写仿函数。
//自定义数据类型，Data类
class Data
{
public:
Data(int i, int d) :id(i), data(d) {}
~Data() {}
int getId() { return id; }
int getData() { return data; }
private:
int id;
int data;
};
//重写仿函数，完成less的功能，也可以用class定义类，此时需要将运算符重载函数设为public
//结构体struct中默认是访问类型是public
struct cmp
{
bool operator() ( Data &a, Data &b) {
return a.getId() < b.getId();
}
};
int main(void){
priority_queue<Data, vector<Data>, cmp > priQueMaxFirst;//该优先级队列维护一个大顶堆，因此最大的元素最先出队
...//一系列操作
...
return 0;
}
运算符重载的话，由于是重载双目运算符，因此需要使用友元函数，我们在类内声明友元函数，在类外实现友元函数，如下：
//自定义数据类型，Data类
class Data
{
public:
Data(int i, int d) :id(i), data(d) {}
~Data() {}
int getId() { return id; }
int getData() { return data; }
friend bool operator < (const Data &a, const Data &b);//运算符重载，友元函数可以访问类的私有成员
private:
int id;
int data;
};
//重载“<”运算符，仿函数less中需要使用
bool operator < (const Data &a, const Data &b) {
return a.id < b.id;
}
int main(void){
priority_queue<Data, vector<Data>, less<Data> > priQueMaxFirst;//该优先级队列维护一个大顶堆，因此最大的元素最先出队
...//一系列操作
...
return 0;
}
优先级队列的基本操作与普通队列类似，不同的是每次获得队内的元素是优先级最高的元素（要从堆的顶部开始），因此使用的是top()方法，而不是front()方法。如下：
程序中，使用基本数据类型“string”以及自定义数据类型Data，分别构造了优先级队列。然后通过运算符重载和重写仿函数来支持自定义的数据类型（两种方法都写了，代码中用的是运算符重载）。
#include <iostream>
#include <queue>//使用队列需要引用<queue>头文件
#include <string>
using namespace std;
//自定义数据类型，Data类
class Data
{
public:
Data(int i, int d) :id(i), data(d) {}
~Data() {}
int getId() { return id; }
int getData() { return data; }
friend bool operator < (const Data &a, const Data &b);//运算符重载，友元函数可以访问类的私有成员
private:
int id;
int data;
};
//重载“<”运算符，仿函数less中需要使用
bool operator < (const Data &a, const Data &b) {
return a.id < b.id;
}
//重写仿函数，完成less的功能，用class的时候，需要public关键词（因为struct中默认数据是public，而class中默认是private）
class cmp
{
public:
bool operator() ( Data &a, Data &b) {
return a.getId() < b.getId();
}
};
int main()
{
//基本数据类型示例
priority_queue<string, vector<string>, greater<string> > p;//维护一个小顶堆，最小的元素优先级最高，最先出队
p.push("C");
p.push("B");
p.push("A");
cout << p.top() << endl;//队列中优先级最高的是最后进队的“A”
//自定义数据类型示例
priority_queue<Data, vector<Data>, less<Data> > priQueMaxFirst;//该优先级队列维护一个大顶堆，因此最大的元素最先出队
//构造一个优先级队列
for (int i = 0; i < 4; ++i) {
Data tmpData(i, 0 - i);
priQueMaxFirst.push(tmpData);
}
//打印当前队列中优先级最高的元素，然后将其出队
while (!priQueMaxFirst.empty()) {
Data topData = priQueMaxFirst.top();//top()与pop()搭配，获得队列中优先级最高的元素，然后将其出队
priQueMaxFirst.pop();
cout << "ID: " << topData.getId() << " " << " Data: " << topData.getData() << endl;//打印当前队列中优先级最高的元素
}
return 0;
}上述程序的输出如下：
