C++:优先级队列

目录

1. 概念

2. 特征

3. 优先级队列的使用

---

1. 概念

优先级队列虽然名字有队列二字，但根据队列特性来说优先级队列不满足先进先出这个特征，优先级队列的底层是用堆来实现的。

优先级队列是一种容器适配器，就是将特定容器类封装作为其底层容器类。

2. 特征

这是优先级队列的模板参数，第一个是具体元素的类型，第二个是实现底层连接的容器，默认是vector，第三个则是改变优先级的参数了，这里默认是仿函数less。对于此处仿函数的使用可以参考下面的文章 ：C++：仿函数-CSDN博客

这里特定容器的选择需满足以下条件：

empty()：检测容器是否为空

size()：返回容器中有效元素个数

front()：返回容器中第一个元素的引用

push_back()：在容器尾部插入元素

pop_back()：删除容器尾部元素

以及改容器可以通过随机访问迭代器访问，因为建堆是需要通过子节点找到父节点或通过父节点找子节点。

综合以上条件，有vector和deque满足。

注意：priority_queue包含在queue的头文件中。

3. 优先级队列的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成 堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。

常用参数	作用
empty()	判断是否为空
size()	优先级队列的长度
push()	向队尾插入数据
pop()	删除顶部数据
swap()	交换两个数据
top()	返回优先级队列中最大(最小元素)，即堆顶元素

下面的代码中当我们只写一个参数时，后两个模板参数默认为vector和less（大堆）

int main()
{int num[] = { 3,5,7,1,9,4 };priority_queue<int> pq(num, num + sizeof(num) / sizeof(int));while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}

我们每次删除或插入数据后，都会将优先级队列重新建堆，保证优先级最高的元素始终在顶部。

注意：如果priority_queue中放的是自定义类型，那需要我们先写出这个自定义类型的 < 和 > 的重载函数。

如果优先级队列中放的是一个开辟空间的节点，那么就必须自己写一个仿函数

下面代码中用的是库函数中的仿函数，那么此时因为仿函数中比较的的是指针，也就是空间的大小，而每次开辟的空间大小都是随机的，所以我们每次运行的结果都是不同的；

这里Less是模拟库函数中的less

template<class T>
class Less
{
public:bool operator()(const T& a, const T& b){return a < b;}
};
int main()
{priority_queue<Date*, vector<Date*>, Less<Date*> > pq;pq.push(new Date(2004, 7, 10));pq.push(new Date(2004, 6, 10));pq.push(new Date(2004, 8, 10));while (!pq.empty()){cout << *pq.top() << " ";pq.pop();}cout << endl;
}

解决的办法就是我们手动写一个专属于Date类的仿函数LessDate，返回解引用的比较，此时比较的就是实际的数了。

class LessDate
{
public:bool operator()(const Date* a, const Date* b){return *a < *b;}
};
int main()
{priority_queue<Date*, vector<Date*>,LessDate > pq;pq.push(new Date(2004, 7, 10));pq.push(new Date(2004, 6, 10));pq.push(new Date(2004, 8, 10));while (!pq.empty()){cout << *pq.top() << " ";pq.pop();}cout << endl;
}