C++ STL priority queue and heap

Posted by chunyang on April 8, 2019
TAGS: #cpp

简介

heap

对于支持 RandomAccessIterator 的容器适用。默认构造最大堆。

  • push_heap
    • 元素放在末尾,然后 __push_heap
  • pop_heap
    • pop 元素会放在末尾,然后插入末尾的元素
  • make_heap
    • [0, n/2) 不断地去 __adjust_heap
  • sort_heap
    • 不断地调用 pop_heap

__push_heap

假定已经是一个 heap 了,新插入的元素在末尾,不断地和它的 parent 比较,如果比

  • __value > *_parent: 则递归往上找,当前节点替换为其 parent 的值
  • __value <= *_parent: 则停止,找到所要插入的位置,插入元素即可
 template <class _RandomAccessIterator, class _Distance, class _Tp>
 void
 __push_heap(_RandomAccessIterator __first,
             _Distance __holeIndex, _Distance __topIndex, _Tp __value)
 {
   _Distance __parent = (__holeIndex - 1) / 2;
   while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
     *(__first + __holeIndex) = *(__first + __parent);
     __holeIndex = __parent;
     __parent = (__holeIndex - 1) / 2;
   }
   *(__first + __holeIndex) = __value;
 }

__adjust_heap

当移除一个元素时,需要找到它的替代元素。不断找左右孩子中较大的:

  • 将移除位置不断和它孩子中较大的元素交换,直至到最后的结尾
    • 这一步确保从 holeIndex 到下面是满足 heap 的顺序结构的
  • 然后再把元素插入到末尾
template <class _RandomAccessIterator, class _Distance, class _Tp>
void
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
              _Distance __len, _Tp __value)
{
  _Distance __topIndex = __holeIndex;
  _Distance __secondChild = 2 * __holeIndex + 2;
  while (__secondChild < __len) {
    if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
      __secondChild--;
    *(__first + __holeIndex) = *(__first + __secondChild);
    __holeIndex = __secondChild;
    __secondChild = 2 * (__secondChild + 1);
  }
  if (__secondChild == __len) {
    *(__first + __holeIndex) = *(__first + (__secondChild - 1));
    __holeIndex = __secondChild - 1;
  }
  __push_heap(__first, __holeIndex, __topIndex, __value);
}

priority queue

优先级队列实际上 stl_heap 中提供几种接口的一种封装。其模板有 3 个参数: priority_queue<_Tp, _Sequence, _Compare>

默认情况下:

  • _Sequence = vector
  • _Compare = less

其提供的接口和 stack 比较类似:

  • push
  • pop
  • top

应用

  • 堆排序
  • 合并 K 个有序数组或者队列
  • Dijstra 算法:单源最短路径

本文完


Creative Commons License
This work is licensed under a CC A-S 4.0 International License.