跳到主要内容C++ priority_queue 优先级队列详解与模拟实现 | 极客日志C++算法
C++ priority_queue 优先级队列详解与模拟实现
介绍 C++ 中 priority_queue 优先级队列的原理与使用。内容包括其作为容器适配器的特性、底层堆结构、仿函数控制大小堆、模拟实现（插入向上调整、删除向下调整）以及典型应用场景。此外还讲解了反向迭代器的适配器设计模式与重载运算符实现。
菩提7 浏览 优先级队列
什么是优先级队列
优先队列也是一种容器适配器（容器适配器即将特定容器类如 vector、list 等封装作为其底层容器类），根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
严格弱序的三条要求：
- 两个关键字不能同时'严格弱序'于对方
- 如果 a'严格弱序'于 b，且 b'严格弱序'于 c，则 a 必须'严格弱序'于 c
- 如果存在两个关键字，任何一个都不'严格弱序'于另一个，则这两个关键字是相等的。
由此看来，优先级队列的性质类似于堆，可以在堆中随时插入元素，并且只能检索到当前所有元素的最大值或最小值（堆顶元素）。
优先队列被实现为容器适配器，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的'尾部'弹出，其称为优先队列的顶部。
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作:
- empty()：检测容器是否为空
- size()：返回容器中有效元素个数
- front()：返回容器中第一个元素的引用
- push_back()：在容器尾部插入元素
- pop_back()：删除容器尾部元素
注意到标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用 vector。需要支持随机访问迭代器，以便始终在内部保持堆结构，容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作。
priority_queue 的使用
优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下 priority_queue 是大堆。
这里如何控制大堆小堆呢？？？
#include <vector>
#include <queue>
#include <functional>
void TestPriorityQueue() {
std::vector<int> v{3, 2, 7, 6, 0, 4, 1, , , };
std::priority_queue<> q1;
(& e : v) q(e);
std::cout << q() << std::endl;
std::priority_queue<, std::vector<>, std::greater<>> (v.(), v.());
std::cout << q() << std::endl;
}
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
9
8
5
int
for
auto
1.
push
1.
top
int
int
int
q2
begin
end
2.
top
如果在 priority_queue 中放自定义类型的数据，我们需要在自定义类型中提供 > 或者 < 的重载。
- 模版参数 1 是 储存的数据类型
- 模版参数 2 是 底层结构，一般使用 vector 或 deque
- 模版参数 3 是 仿函数，提供比较方式（建大堆，还是建小堆）
可以看到是通过仿函数逻辑来实现大堆小堆的，下面我们开始仿函数的学习使用。
仿函数
仿函数是什么？一看名字可能以为是函数，事实上仿函数（Functor）是指一种重载了 operator() 运算符的类，可以像函数一样使用对象。这种设计使得对象可以具有类似于函数的行为，仿函数通常用于实现更复杂的函数逻辑。
void qsort (void* base, size_t num, size_t size,int (*compar)(const void*,const void*));
其最后一个参数就是函数指针，说实话比较复杂，因为我们在实现函数功能时并不知道会是什么类型，所以就很复杂。而我们通过仿函数，可以使用模版类，然后就自然适配所有的类型：
template<class T> struct less {
bool operator()(const T& a, const T& b) { return a < b; }
};
template<class T> struct greater {
bool operator()(const T& a, const T& b) { return a > b; }
};
- 灵活性：可以使用对象存储状态，而函数本身无法做到这一点。这允许在仿函数中存储更多的上下文信息。
- 可组合性：仿函数可以作为其他算法和函数模板的参数。
- 高效性：在一些 STL 算法中使用仿函数，可以提高代码执行效率，特别是在需要内联函数调用时。
priority_queue 的模拟实现
整体框架接口
namespace qsy {
template<class T> struct less {
bool operator()(const T& a, const T& b) { return a < b; }
};
template<class T> struct greater {
bool operator()(const T& a, const T& b) { return a > b; }
};
template<class T, class Container = std::vector<T>, class compare = less<T> >
class priority_queue {
public:
priority_queue() {};
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last) {}
void AdjustUp() {}
void push(const T& x) {}
void AdjustDown() {}
void pop() {}
size_t size() const {}
T& top() { }
bool empty() {}
private:
Container _con;
};
}
插入&&向上调整
插入的操作很简单，容器调用 push_back 即可，但是我们需要位置优先级队列（堆）的结构就需要将元素进行向上调整。
void AdjustUp(int size)
{
compare com;
int child = size - 1;
int parent = (child - 1) / 2;
while (child > 0) {
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
} else break;
parent = (child - 1) / 2;
}
}
void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size());
}
删除&&向下调整
注意删除操作是对堆顶的删除，但是容器的删除操作一般都是尾删，所以要先将容器的首元素与结尾位置进行交换，交换后尾差即可。然后进行向下调整，维持优先队列（堆）的特性。
void AdjustDown(int parent)
{
compare com;
int child = 2 * parent + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && com(_con[child], _con[child+1])) {
child = child + 1;
}
if (com(_con[parent], _con[child])) {
swap(_con[child], _con[parent]);
parent = child;
child = 2 * parent + 1;
} else break;
}
}
void pop() {
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
其他接口
size_t size() const { return _con.size(); }
T& top() { return _con[0]; }
bool empty() { return _con.empty(); }
这里注意一下如何将一组无序数据建堆，对应的接口就是迭代器构造。
priority_queue() : _con() {}
template<class Iterator>
priority_queue(Iterator first, Iterator last) : _con(first, last) {
int count = _con.size()-1;
int root = ((count - 1)/ 2);
for (; root >= 0; root--) AdjustDown(root);
}
优先级队列的应用
C++ 中的优先队列（priority_queue）是一种容器适配器，它提供了常数时间复杂度的元素插入操作和 logN 时间复杂度的元素删除操作。由于它是基于堆实现的，所以非常适合用于需要频繁地找到最大或最小元素的应用场景。以下是一些典型的使用场景：
- 任务调度：在操作系统中，优先队列可以用来实现任务调度器（Linux 下是使用优先队列），确保高优先级的任务先被执行。
- 图算法：
- Dijkstra 算法：优先队列用于找出最短路径。
- Prim 算法：在生成最小生成树时，优先队列用于选择最小的边。
- 数据流处理：在处理数据流时，如在线广告投放系统，可以使用优先队列来选择价值最高的广告进行展示。
- 事件模拟：在模拟系统中，优先队列可以用来按时间顺序处理事件，比如网络中的数据包传输。
- 霍夫曼编码：在构建霍夫曼树时，优先队列用来按照频率排序字符。
- 多路归并：在数据合并操作中，优先队列可以帮助实现多路归并算法，例如在数据库索引的构建中。
- 堆排序：优先队列可以作为堆排序算法的实现基础。
- 选择问题：例如，快速选择算法可以使用优先队列来找到第 k 大的元素。
- 资源分配：在网络路由算法中，优先队列可以用来决定数据包的传输路径。
- 游戏开发：在游戏 AI 中，优先队列可以用来确定下一步的行动，基于行动的优先级进行排序。
优先队列的使用非常灵活，它适合于任何需要动态调整元素优先级和快速访问最高（或最低）优先级元素的场景。在使用时，需要注意其插入和删除操作的时间复杂度，以及如何根据实际需求选择合适的仿函数。
反向迭代器
在复刻 STL 中的 list 容器时，首次采用了类封装的方式来构建迭代器，以此实现迭代器的递增、递减和元素访问功能。然而，当我们面临实现反向迭代器的需求时，是否需要重头开始，再次进行类的封装呢？
显然这种做法并非必要（不然就要手搓无数个反向迭代器了）。因为反向迭代器与正向迭代器在功能上存在高度一致性，唯一的区别在于它们在容器中的移动方向相反。因此，我们可以采用适配器设计模式，对现有的正向迭代器进行二次封装，以此满足反向迭代器的需求。
通过引入适配器，我们不仅可以避免重复造轮子的工作，还能够提升代码的复用性和简洁性。这种设计模式的应用，使得我们能够在保持代码高效和可维护性的同时，轻松实现反向迭代器的功能。
template <class RandomAccessIterator, class T, class Reference = T&, class Distance = ptrdiff_t>
class reverse_iterator {
typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance> self;
protected:
RandomAccessIterator current;
public:
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef Reference reference;
} ;
这里我们选择三个模板参数复刻学习，事实上也可以一个模板参数通过迭代器萃取。
typedef reverse_bidirectional_iterator<const_iterator, value_type, const_reference, difference_type> const_reverse_iterator;
typedef reverse_bidirectional_iterator<iterator, value_type, reference, difference_type> reverse_iterator;
namespace qsy {
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator {
typedef ReverseIterator<Iterator, Ref, Ptr> Self;
ReverseIterator(Iterator it) :_it(it) {}
Iterator _it;
};
}
反向迭代器与正向迭代器在功能上相似，都用于遍历容器中的元素。然而，它们在操作方向上存在显著差异：
- 正向迭代器通过 ++ 运算符向前移动，而反向迭代器则通过 – 运算符向后移动。
实现反向迭代器的基本方法是通过编写一个类模板，该模板会被编译器用来生成具体容器对应的迭代器实例。在这个过程中，编译器负责实例化这些迭代器，从而提供一种便捷的方式来反向遍历容器中的元素。
重载运算符
Self& operator++() { --_it; return *this; }
Self& operator++(int) { Self tmp = _it; --_it; return tmp; }
Self& operator--() { ++_it; return *this; }
Self& operator--(int) { Self tmp = _it; ++_it; return tmp; }
对于反向迭代器的 == != 操作实质上也就是其封装的正向迭代器的比较：
bool operator!=(const Self& s) { return _it != s._it; }
bool operator==(const Self& s) { return _it == s._it; }
Ref operator*() {
Iterator tmp = _it;
return *--tmp;
}
Ptr operator->() { return &(operator*()); }
为什么这里的访问要有 -- 操作？？？因为为了与正向迭代器对称，反向迭代器的开始位置并不是结尾，而是哨兵位。
下面这种可以直接使用已有的 end() , begin() 函数进行复用，增加代码可读性。所以对应的访问方式就要减一再访问。效果其实两种区别不大，但是第二种的代码更加简洁。
容器的反向迭代器使用
这里需要 typedef 简化一下 然后提供 相应的 rbegin rend 就可以复用了。
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rbegin()const { return const_reverse_iterator(end()); }
const_reverse_iterator rend()const { return const_reverse_iterator(begin()); }
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin()const { return _start; }
const_iterator end()const { return _finish; }
int main() {
qsy::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
qsy::vector<int>v(lt.begin(), lt.end());
auto rit = v.rbegin();
while(rit != v.rend()) {
std::cout << *rit << ' ';
++rit;
}
std::cout << std::endl;
}
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rbegin()const { return const_reverse_iterator(end()); }
const_reverse_iterator rend()const { return const_reverse_iterator(begin()); }
iterator begin()
{
return _head->_next;
}
const_iterator begin()const
{
return _head->_next;
}
const_iterator cbegin()const { return _head->_next; }
iterator end() { return _head;
const_iterator end()const { return _head; }
const_iterator cend()const { return _head; }
#define _CRT_SECURE_NO_WARNINGS
#include"vector.h"
#include"list.h"
int main() {
qsy::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
qsy::vector<int>v(lt.begin(), lt.end());
auto rit = v.rbegin();
auto rrit = lt.rbegin();
while(rrit != lt.rend()) {
std::cout << *rrit << ' ';
++rrit;
}
std::cout << std::endl;
}
其他模板容器均可以通过这样的方式实现反向迭代器，是一种封装的思想。
