STL中的优先级队列和堆问题

priority_queue 是容器适配器,它提供常数时间的(默认)最大元素查找,对数代价的插入与释出。

可用用户提供的 Compare 更改顺序,例如,用 std::greater 将导致最小元素作为 top() 出现。

priority_queue 工作类似管理某些随机访问容器中的,优势是不可能突然把堆非法化。

默认情况下priority_queue内部是以”降序“排列的,即默认大顶堆

一、使用

定义于头文件

1
2
3
4
5
template<     
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;

模板形参

堆实现

大顶堆:priority_queue默认实现大顶堆,也可将priority_queue模板第三个参数显示设置 std::less

小顶堆:priority_queue模板第三个参数显示设置 std::greater,实现小顶堆。

二、priority_queue自定义排序

前面说到 priority_queue 容器适配器时,还遗留一个问题,即当 头文件提供的排序方式(std::less 和 std::greater)不再适用时,如何自定义一个满足需求的排序规则。

首先来看看 std::less 和 std::greater 各自的底层实现。实际上, 头文件中的 std::less 和 std::greater ,各自底层实现采用的都是函数对象的方式。

比如,std::less 的底层实现代码为:

1
2
3
4
5
6
7
template <typename T>
struct less {
//定义新的排序规则
bool operator()(const T &_lhs, const T &_rhs) const {
return _lhs < _rhs;
}
};

std::greater 的底层实现代码为:

1
2
3
4
5
6
template <typename T>
struct greater {
bool operator()(const T &_lhs, const T &_rhs) const {
return _lhs > _rhs;
}
};

可以看到,std::less 和 std::greater 底层实现的唯一不同在于,前者使用 < 号实现从大到小排序,后者使用 > 号实现从小到大排序。

仿照 std::less 和 std::greater 的底层实现代码,我们可以自己定义比较函数,然后作为参数传入priority_queue使用。

参考文章

cppreference::priority_queue

STL priority_queue自定义排序实现方法详解

Author: wnxy
Link: https://wnxy.github.io/2021/06/28/Priority_queue_and_heap/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.