本文原创
queue 是 FIFO 结构，先进的元素一定先出，在某些场合需要对出队的元素进行紧急性出队排序，因此称为优先队列，可以使得权值最大或最小的元素最先出队。
因为 priority_queue 内部维护了一个堆，堆中元素的优先性可以指定仿函数自定义，所以不需要用到 pop_front() 成员函数，因此 priority_queue 内部结构慰由 vector 实现，默认的排序规则使用使用 STL 自带的 less<> 函数算子：
template <class _Tp,
class _Sequence = vector<_Tp>,
class _Compare = less<typename _Sequence::value_type> >
class priority_queue
{
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
protected:
_Sequence c;
_Compare comp;
public:
priority_queue() : c() {}
explicit priority_queue(const _Compare& __x) : c(), comp(__x) {}
priority_queue(const _Compare& __x, const _Sequence& __s) : c(__s), comp(__x)
{ make_heap(c.begin(), c.end(), comp); }
priority_queue(const value_type* __first, const value_type* __last) : c(__first, __last)
{ make_heap(c.begin(), c.end(), comp); }
priority_queue(const value_type* __first, const value_type* __last, const _Compare& __x) : c(__first, __last), comp(__x)
{ make_heap(c.begin(), c.end(), comp); }
priority_queue(const value_type* __first, const value_type* __last,
const _Compare& __x, const _Sequence& __c) : c(__c), comp(__x)
{
c.insert(c.end(), __first, __last);
make_heap(c.begin(), c.end(), comp);
}
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const_reference top() const { return c.front(); }
void push(const value_type& __x)
{
__STL_TRY {
c.push_back(__x);
push_heap(c.begin(), c.end(), comp);
}
__STL_UNWIND(c.clear());
}
void pop()
{
__STL_TRY {
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
__STL_UNWIND(c.clear());
}
};
上述成员变量 c 默认就是一个 vector，该 vector 被构建成了一个堆，因此 top() 函数返回 vector 起始元素，priority_queue 涉及到的 push_heap、make_heap、pop_heap 操作在头文件 stl_heap.h 中定义，下面最简单的 push_heap 进行分析，下图的虚线结点为刚刚 push_back 进 vector 的元素，插入新结点前的 vector 已经是一个大顶堆：
/* 以上图为例，因为 7 < 15，因此距离 first 为 10 的结点先被其父结点 4 赋值，仍然 14 < 15，
结点 4 被其父结点 1 赋值，现在 16 >= 15，退出 while 循环，结点 1 就是新结点 10 调整至的位置 */
template <class _RandomAccessIterator, class _Distance, class _Tp, class _Compare>
void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __topIndex, _Tp __value, _Compare __comp)
{
_Distance __parent = (__holeIndex - 1) / 2; // 得到待插入结点的 parent 到 first 的距离
/* 往根结点方向追溯，不断让比 __value 小的结点往叶子结点方向调整，
直至碰到一个结点不小于 __value 的结点，把新结点插入成为该结点的子结点 */
while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value))
{
*(__first + __holeIndex) = *(__first + __parent); // 子结点的值成为 parent 结点的值
__holeIndex = __parent; // vector 中游标调整，相当于堆中原先指向子结点的指针指向父结点
__parent = (__holeIndex - 1) / 2; // 父结点指针调整为原先父结点的父结点
}
*(__first + __holeIndex) = __value; // 在堆中该适当位置填入新结点
}
template <class _RandomAccessIterator, class _Compare, class _Distance, class _Tp>
inline void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp, _Distance*, _Tp*)
{
__push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
_Tp(*(__last - 1)), __comp); // 第二个实参为新插入元素到 first 的距离
}
template <class _RandomAccessIterator, class _Compare>
inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
__push_heap_aux(__first, __last, __comp,
__distance_type(__first), __value_type(__first)); // traits 技巧的使用
}
接着对 pop_heap 操作进行分析， 观察 priority_queue 的 pop() 函数是先进行 pop_heap 再对其 vector 进行 pop_back()，因此 pop_heap 的操作就把根结点的值赋给最后一个叶子结点，随后把该叶子结点从堆中排除后，对堆进行调整，同样地，pop_heap 是多层调用：
template <class _RandomAccessIterator, class _Tp, class _Compare, class _Distance>
inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_RandomAccessIterator __result, _Tp __value, _Compare __comp,
_Distance*)
{
*__result = *__first; // 把根结点的值赋给最末尾结点的值，最后 pop_back() 便可直接取到
__adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value, __comp);
}
template <class _RandomAccessIterator, class _Tp, class _Compare>
inline void __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Tp*, _Compare __comp)
{
__pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)),
__comp, __distance_type(__first)); // 传递最末尾的结点的位置和存储值
}
template <class _RandomAccessIterator, class _Compare>
inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
__pop_heap_aux(__first, __last, __value_type(__first), __comp);
}
上述 __adjust_heap 操作就是对排除掉最末尾结点后的堆进行调整，使其仍满足堆的要求，可结合下述例子进行分析，待 pop 的原始堆：
__adjust_heap 函数中直至进入 push_heap 之前时的堆演变过程：
push_heap操作之后的最终结果：
__adjust_heap 操作的代码如下：
template <class _RandomAccessIterator, class _Distance, class _Tp, class _Compare>
void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __len, _Tp __value, _Compare __comp)
{
_Distance __topIndex = __holeIndex; // 存储根结点的位置
_Distance __secondChild = 2 * __holeIndex + 2; // 取得右孩子结点的位置
while (__secondChild < __len) // 未超出堆的大小范围
{
/* 让 __secondChild 游标指向两个孩子结点中较大的那个结点 */
if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
__secondChild--;
*(__first + __holeIndex) = *(__first + __secondChild); // 较大子结点值覆盖父结点值
__holeIndex = __secondChild; // 父结点游标更新为子结点游标
__secondChild = 2 * (__secondChild + 1); // 子结点游标更新为其自身的右孩子结点
}
if (__secondChild == __len) // 如果最终的右孩子结点刚好是待 pop() 的结点
{
*(__first + __holeIndex) = *(__first + (__secondChild - 1)); // 只能取左孩子结点了
__holeIndex = __secondChild - 1; // 父结点游标仍要更新为子结点游标
}
/* 现在去除根结点后的堆已经调整完毕，需要把第一次被根结点覆盖掉的原最末尾结点重新插入到堆中 */
__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
}
make_heap 操作从 vector 中间位置的结点递减至起始结点，逐个地作 __adjust_heap 操作：
template <class _RandomAccessIterator, class _Compare, class _Tp, class _Distance>
void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp, _Tp*, _Distance*)
{
if (__last - __first < 2) return; // 如果 vector 只含一个元素
_Distance __len = __last - __first; // 获得 vector 中元素的个数
_Distance __parent = (__len - 2) / 2; // 位于 vector 中间位置的元素
while (true)
{
__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)), __comp);
if (__parent == 0) return;
__parent--; // 往起始结点方向逐个移动
}
}
template <class _RandomAccessIterator, class _Compare>
inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
__make_heap(__first, __last, __comp,
__vaule_type(__first), __distance_type(__first)); // traits
}
该算法的正确性参见《算法导论》第 132 页采用循环不变式的证明。
在此顺便将堆排序的算法 sort_heap 代码贴上：
template <class _RandomAccessIterator, class _Compare>
void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
while (__last - __first > 1)
pop_heap(__first, __last--, __comp);
}
每一次 pop_heap 都是将根结点的值 pop 出来，实质是放到 vector 最后，直至只剩一个结点为止，若是大顶堆，得到的就是一个升序序列，若是小顶堆，得到的就是一个降序序列。