Priority_queue的使用

注意

排序思路不同<代表的是大顶堆，因为如果小于为true，则代表小的元素会下浮，那么大的就会在堆顶，而>代表的是小顶堆，是因为大的元素下浮了
C++中，使用优先级队列需要包含头文件
不会自动排序。如果修改了优先级队列中某元素的值，则需要重新排序。因此，需要删除特定元素时，使用set更好

定义

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;

自定义排序

重载运算符()

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

重载运算符<

//重载“<”运算符，仿函数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()方法。如下：

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