本文原创
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 最后,直至只剩一个结点为止,若是大顶堆,得到的就是一个升序序列,若是小顶堆,得到的就是一个降序序列。