送给大家一句话:
这世上本来就没有童话，微小的获得都需要付出莫大的努力。
– 简蔓 《巧克力色微凉青春》
开始使用优先队列
- 1 前言
- 2 优先队列
- 2.1 什么是优先队列
- 2.2 使用手册
- 2.3 仿函数
- 3 优先队列的实现
- 3.1 基本框架
- 3.2 插入操作
- 3.3 删除操作
- 3.4 其他函数
- 4 总结
- Thanks♪(･ω･)ﾉ谢谢阅读！！！
- 下一篇文章见！！！
1 前言
上一篇文章我们实现了stack 与 queue 。接下来我们来认识一个新的容器：优先队列。优先队列具有一些与众不同的特性，也会涉及一种新的事物：仿函数。接下来我们一起来看看吧！
2 优先队列
2.1 什么是优先队列
优先队列是一种容器适配器（容器适配器即将 特定容器类 （vector list 等等）封装作为其底层容器类 ），根据严格的弱排序标准，它的第一个元素总是所以元素中最大的！
弱排序标准
1. 两个关键字不能同时“严格弱序”于对方
2. 如果a“严格弱序”于b，且b“严格弱序”于c，则a必须“严格弱序”于c
3. 如果存在两个关键字，任何一个都不“严格弱序”于另一个，则这两个关键字是相等的。
也就是其性质类似与“堆”，可以在堆中随时插入元素，并且只能检索到当前所以元素的最大值或最小值（堆顶元素）。
优先队列 被实现为 容器适配器，queue提供一组特定的成员函数来访问其元素。元素从特定容器的"尾部"弹出，其称为优先队列的顶部。
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作:
- empty()：检测容器是否为空
- size()：返回容器中有效元素个数
- front()：返回容器中第一个元素的引用
- push_back()：在容器尾部插入元素
- pop_back() : 删除容器尾部元素
标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
2.2 使用手册
| 函数声明 | 接口说明 |
|---|---|
| priority_queue()/priority_queue(first,last) | 构造一个空的优先级队列 |
| empty( ) | 检测优先级队列是否为空，是返回true，否则返回false |
| top( ) | 返回优先级队列中最大(最小元素)，即堆顶元素 |
| push(x) | 在优先级队列中插入元素x |
| pop() | 删除优先级队列中最大(最小)元素，即堆顶元素 |
使用起来还是很简单的。
但是注意一下创建的时候需要将模版参数传够
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
- 模版参数 1 是 储存的数据类型
- 模版参数 2 是 底层结构，一般使用vector 或 deque
- 模版参数 3 是 仿函数，提供比较方式（建大堆，还是建小堆），下文我们来学习仿函数
2.3 仿函数
仿函数顾名思义是：类似函数但不是函数。
它是如何实现的呢？？？ 使用类中的将（）操作符重载。就通过这样的类操作符的使用规避了函数指针。先前我们C语言的qsort 函数：
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;
}
};
通过这个仿函数可以轻松顶替复杂的函数指针。
3 优先队列的实现
3.1 基本框架
以下是优先队列的大概框架：
namespace bit
{
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 = 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;
//仿函数实例化
compare com;
};
}
我们接下来逐个来实现
3.2 插入操作
插入很简单，在容器尾push_back()一个新元素就可以，但是为了保持优先队列的特性我们需要对刚刚插入的元素进行向上调整，将其放在合适的位置上：
void AdjustUp()
{
// 1 2 3 4 5 6 7 8 9
// 0
// / \
// 1 2
// / \ / \
// 3 4 5 6
// / \
// 7 8
//孩子节点是刚插入的节点
int child = _con.size() - 1;
//父节点通过规律寻得 （看图分析就可以）
int parent = (child - 1) / 2;
//调整
while (parent >= 0)
{
//谁大（小）谁当父节点
if (com(_con[parent] , _con[child]))
{
swap(_con[parent], _con[child]);
//更新节点
child = parent;
parent = (child - 1) / 2;
}
//反之不需要调整
else
{
break;
}
}
}
void push(const T &x)
{
_con.push_back(x);
AdjustUp();
}
3.3 删除操作
注意删除操作是对堆顶的删除，但是容器的删除操作一般都是尾删，所以要先将容器的首元素与结尾位置进行交换，交换后尾差即可。然后进行向下调整，维持优先队列的特性。
void AdjustDown()
{
// 1 2 3 4 5 6 7 8 9
// 8
// / \
// 1 2
// / \ / \
// 3 4 5 6
// / \
// 7 [0]删除掉
//父节点
int parent = 0;
//孩子节点
int child = parent * 2 + 1;
if (child + 1< _con.size() && com(_con[child], _con[child + 1]))
{
child++;//选择最合适的子节点
}
//调整
while (child < _con.size() )
{
//谁大（小）谁当父节点
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
//更新父子节点
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
//交换后在删除
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown();
}
3.4 其他函数
其他函数直接使用底层容器进行返回就可以
size_t size() const
{
return _con.size();
}
T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
4 总结
C++中的优先队列（priority_queue）是一种容器适配器，它提供了常数时间复杂度的元素插入操作和 logarithmic 时间复杂度的元素删除操作。由于它是基于堆实现的，所以非常适合用于需要频繁地找到最大或最小元素的应用场景。以下是一些典型的使用场景：
- 任务调度：在操作系统中，优先队列可以用来实现任务调度器（Linux下是使用优先队列），确保高优先级的任务先被执行。
- 图算法：
- Dijkstra算法：优先队列用于找出最短路径。
- Prim算法：在生成最小生成树时，优先队列用于选择最小的边。
- 数据流处理：在处理数据流时，如在线广告投放系统，可以使用优先队列来选择价值最高的广告进行展示。
- 事件模拟：在模拟系统中，优先队列可以用来按时间顺序处理事件，比如网络中的数据包传输。
- 霍夫曼编码：在构建霍夫曼树时，优先队列用来按照频率排序字符。
- 多路归并：在数据合并操作中，优先队列可以帮助实现多路归并算法，例如在数据库索引的构建中。
- 堆排序：优先队列可以作为堆排序算法的实现基础。
- 选择问题：例如，快速选择算法可以使用优先队列来找到第k大的元素。
- 资源分配：在网络路由算法中，优先队列可以用来决定数据包的传输路径。
- 游戏开发：在游戏AI中，优先队列可以用来确定下一步的行动，基于行动的优先级进行排序。
优先队列的使用非常灵活，它适合于任何需要动态调整元素优先级和快速访问最高（或最低）优先级元素的场景。在使用时，需要注意其插入和删除操作的时间复杂度，以及如何根据实际需求选择合适的仿函数。
