目录
1. priority_queue介绍
①. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
②. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
③. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
④. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
- empty()：检测容器是否为空
- size()：返回容器中有效元素个数
- front()：返回容器中第一个元素的引用
- push_back()：在容器尾部插入元素
- pop_back()：删除容器尾部元素
⑤. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
⑥. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
2.堆的向上和向下调整算法
- priority_queue的底层实际上就是堆结构
(1)堆的向上调整算法
调整的基本思想如下：
- 将目标结点与其父结点进行比较。
- 若目标结点的值比父结点的值大，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整；若目标结点的值比其父结点的值小，则停止向上调整，此时该树已经是大堆了。
- 以大堆为例，堆的向上调整算法就是在大堆的末尾插入一个数据后，经过一系列的调整，使其仍然是一个大堆
- 现在有一些数据（49 28 57 34 53 84 83 74 52），经过向上调整之后的顺序是 (84 74 83 53 34 49 57 28 52)
- 现在我们要插入一个数据80，下面是调整过程
代码实现:
//堆的向上调整（大堆）
void AdjustUp(vector<int>& v, int child)
{
size_t parent = (child - 1) / 2; //通过child计算parent的下标
while (child > 0)//调整到根结点的位置截止
{
if (v[parent] < v[child])//孩子结点的值大于父结点的值
{
//将父结点与孩子结点交换
swap(v[child], v[parent]);
//继续向上进行调整
child = parent;
parent = (child - 1) / 2;
}
else//已成堆
{
break;
}
}
}
(2)堆的向下调整算法
- 以大堆为例，使用堆的向下调整算法有一个前提，就是待向下调整的结点的左子树和右子树必须都为大堆。
调整的基本思想如下：
- 将目标结点与其较大的子结点进行比较。
- 若目标结点的值比其较大的子结点的值小，则交换目标结点与其较大的子结点的位置，并将原目标结点的较大子结点当作新的目标结点继续进行向下调整；若目标结点的值比其较大子结点的值大，则停止向下调整，此时该树已经是大堆了。
- 现在我们要获取priority_queue 的堆顶元素( 84 ),然后pop，此时堆需要重新调整成大堆,
- 调整过程如下: 先返回堆顶元素，然后将vector 中的第一个元素和最后一个元素的值交换, 然后vector 进行 pop_back().
代码实现:
//堆的向下调整（大堆）
void AdjustDown(vector<int>& v, int n, int parent)
{
//child记录左右孩子中值较大的孩子的下标
int child = 2 * parent + 1;//先默认其左孩子的值较大
while (child < n) //child不能越界
{
if (child + 1 < n && v[child] < v[child + 1])//右孩子存在并且右孩子比左孩子还大
{
child++;//较大的孩子改为右孩子
}
if (v[parent] < v[child])//左右孩子中较大孩子的值比父结点还大
{
//将父结点与较小的子结点交换
swap(v[child], v[parent]);
//继续向下进行调整
parent = child;
child = 2 * parent + 1;
}
else//已成堆
{
break;
}
}
}
3.priority_queue模拟实现
namespace XM //防止命名冲突
{
//比较方式（使内部结构为大堆）
template<class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
//比较方式（使内部结构为小堆）
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
//优先级队列的模拟实现
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
//堆的向上调整
void AdjustUp(int child)
{
int parent = (child - 1) / 2; //通过child计算parent的下标
while (child > 0)//调整到根结点的位置截止
{
if (_comp(_con[parent], _con[child]))//通过所给比较方式确定是否需要交换结点位置
{
//将父结点与孩子结点交换
swap(_con[child], _con[parent]);
//继续向上进行调整
child = parent;
parent = (child - 1) / 2;
}
else//已成堆
{
break;
}
}
}
//插入元素到队尾（并排序）
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1); //将最后一个元素进行一次向上调整
}
//堆的向下调整
void AdjustDown(int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child + 1 < n&&_comp(_con[child], _con[child + 1]))
{
child++;
}
if (_comp(_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(_con.size(), 0); //将下标为0个元素进行一次向下调整
}
//访问队头元素（堆顶元素）
T& top()
{
return _con[0];
}
const T& top() const
{
return _con[0];
}
//获取队列中有效元素个数
size_t size() const
{
return _con.size();
}
//判断队列是否为空
bool empty() const
{
return _con.empty();
}
private:
Container _con; //底层容器
Compare _comp; //比较方式
};
}(1)关于priority_queue底层堆的调整
- push : 在容器尾部插入元素后进行一次向上调整算法
- pop : 将容器头部和尾部元素交换，再将尾部元素删除，最后从根结点开始进行一次向下调整算法
- 通过push 和 pop 函数底层堆不断进行调整始终保持堆的结构 ；每插入 / 删除 一个元素都要进行堆的调整
(2)仿函数实现比较方式
- 为什么要用仿函数 ， 而不用函数指针 ， 因为函数指针太复杂了，用起来不好
- 通过重载operator()方式实现仿函数
-
默认情况下，priority_queue是大堆
-
如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。
本文含有隐藏内容，请 开通VIP 后查看