1. 优先级队列（priority_queue）

1.1 基本概念

之前已经提到了队列（queue），队列是一种先进先出（First in First out，FIFO）的数据类型。每次元素的入队都只能添加到队列尾部，出队时从队列头部开始出。

优先级队列（priority_queue）其实，不满足先进先出的条件，更像是数据类型中的“堆”。优先级队列每次出队的元素是队列中优先级最高的那个元素，而不是队首的元素。这个优先级可以通过元素的大小等进行定义。比如定义元素越大优先级越高，那么每次出队，都是将当前队列中最大的那个元素出队。个人感觉这就是所谓“优先级”的定义。

现在看优先级队列是不是就是“堆”了，如果最大的元素优先级最高，那么每次出队的就是当前队列中最大的元素，那么队列实际就相当于一个大顶堆，每次将堆根节点元素弹出，重新维护大顶堆，就可以实现一个优先级队列。

1.2 优先级队列的定义

C++中，使用优先级队列需要包含头文件<queue>，优先级队列的定义如下：

priority_queue<typename, container, functional>

typename是数据的类型；
container是容器类型，可以是vector,queue等用数组实现的容器，不能是list，默认可以用vector；
functional是比较的方式，默认是大顶堆（就是元素值越大，优先级越高）；如果使用C++基本数据类型，可以直接使用自带的less和greater这两个仿函数（默认使用的是less，就是构造大顶堆，元素小于当前节点时下沉）。使用自定义的数据类型的时候，可以重写比较函数，也可以进行运算符重载（less重载小于“<”运算符，构造大顶堆；greater重载大于“>”运算符，构造小顶堆）。

定义一个优先级队列的示例如下：

//构造一个大顶堆，堆中小于当前节点的元素需要下沉，因此使用less
priority_queue<int, vector<int>, less<int>> priQueMaxFirst;

//构造一个小顶堆，堆中大于当前节点的元素需要下沉，因此使用greater
priority_queue<string, vector<string>, greater<string>> priQueMinFirst;

1.3 通过重写仿函数来支持自定义数据类型

仿函数是通过重载“()”运算符来模拟函数操作的类。

先自定义一个类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;
}

1.4 通过运算符重载来支持自定义比较函数

运算符重载的话，由于是重载双目运算符，因此需要使用友元函数，我们在类内声明友元函数，在类外实现友元函数，如下：

//自定义数据类型，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;
}

1.5 优先级队列的基本操作

优先级队列的基本操作与普通队列类似，不同的是每次获得队内的元素是优先级最高的元素（要从堆的顶部开始），因此使用的是top()方法，而不是front()方法。如下：

push() ：入队。向队列添加一个元素，无返回值；
pop() ：将队列中优先级最高的元素出队。将队列中优先级最高的元素删除（出队），无返回值；
top() ：获得队列优先级最高的元素。此函数返回值为队列中优先级最高的元素，常与pop()函数一起，先通过top()获得队列中优先级最高的元素，然后将其从队列中删除；
size() ：获得队列大小。此函数返回队列的大小，返回值是“size_t”类型的数据，“size_t”是“unsigned int”的别名。
empty() ：判断队列是否为空。此函数返回队列是否为空，返回值是bool类型。队列空：返回true；不空：返回false。

2. 示例程序

程序中，使用基本数据类型“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;
}

上述程序的输出如下：

C++优先队列_队列queue中添加元素的方法