stl priority_queue源码分析

分析stl sort函数的时候，发现优先级队列挺麻烦的，单独整理一篇

priority_queue

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class _Tp, class _Sequence = vector<_Tp>, 
          class _Compare = less<typename _Sequence::value_type> >
#else
template <class _Tp, class _Sequence, class _Compare>
#endif

看看常用的几个函数的实现：

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());
}

// 不带自定义排序的版本，默认是个最大堆

push_heap

这里添加新元素的方法是：从下往上堆化

• 先往完全二叉树的最后一个节点即随机迭代器的end()插入一个新元素，位置记为hole_index
• 然后逐层往上和父节点比较，如果不满足最大堆的性质就覆盖父节点(这里没有直接swap)，直到top_index也就是堆顶结束

这里传入了value是个值对象，在priority_queue::push_back(tmp)中value就是tmp,是vector的最后一个元素,在priority_queue::pop()中，value是数组原来最后的那个元素，但进到这个函数的时候最后一个元素已经被front()覆盖了，此时比堆化的是一个小数组。如下演示:

// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.

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;   // 这一步很重要，因为value不一定就是back()的元素
}

template <class _RandomAccessIterator, class _Distance, class _Tp>
inline void 
__push_heap_aux(_RandomAccessIterator __first,
                _RandomAccessIterator __last, _Distance*, _Tp*)
{
  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
              _Tp(*(__last - 1)));
}

template <class _RandomAccessIterator>
inline void 
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
  __push_heap_aux(__first, __last,
                  __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
}

pop_heap

移除堆顶元素,这里比较复杂，一般介绍的删除堆顶的方法是:

• 把最后一个元素的值拷贝到堆顶
• 然后删除最后一个元素
• 在接着从堆顶往下堆化更新

但这里却不是这么实现的，简单概括下就是(按照默认的最大堆看)：

• 把堆顶的元素的值拷贝到最后一个元素
• 然后往下查找左右节点，把最大值(更新hole_index为当前的最大值的索引)拷贝到父节点(只比较左右节点，不和父节点比较)
• 如果一直找直到找到了最后一个节点，则把倒数第二个节点(hole_index)拷贝到父节点
• push_heap插入原来被覆盖掉的尾节点back()的值，范围是从first到前面最后那个hole_index

分析：因为第一步用front()覆盖了back(),导致有2个重复的值，并且少了一个value(即原来的back()).后面一直按照com的规则，用最大值覆盖父节点，往下层走，保证上层都是符合堆化规则的。一直找到最后一层的最大值，这个最大值已经被copy然后赋值到上一层了，所以是重复存在的值，这时候相当于用value替换了这个重复的值，然后还是往上堆化.

画了个示意图：

if (__secondChild == __len)这种情况需要特别处理:

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 = 孩子节点的较大值
      __secondChild--;

    *(__first + __holeIndex) = *(__first + __secondChild);  // __secondChild的值赋值给父节点__holeIndex
    __holeIndex = __secondChild;
    __secondChild = 2 * (__secondChild + 1);
  }

  if (__secondChild == __len) {     // 碰到了最后的元素，也就是原来的堆顶元素
    *(__first + __holeIndex) = *(__first + (__secondChild - 1));
    __holeIndex = __secondChild - 1;
  }
  __push_heap(__first, __holeIndex, __topIndex, __value);   // push原来的最后那个元素
}

template <class _RandomAccessIterator, class _Tp, class _Distance>
inline void 
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _RandomAccessIterator __result, _Tp __value, _Distance*)
{
  *__result = *__first;     // 用堆顶元素覆盖最后一个元素
  __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);   // 传入原来最后的元素
}

template <class _RandomAccessIterator, class _Tp>
inline void 
__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
               _Tp*)
{
  __pop_heap(__first, __last - 1, __last - 1, 
             _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
}

template <class _RandomAccessIterator>
inline void pop_heap(_RandomAccessIterator __first, 
                     _RandomAccessIterator __last)
{
  __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
}

make_heap

建堆，步骤：

• 从最后的一个非叶子节点(parent)开始往下堆化，每次用孩子节点的较大值覆盖父节点的值，一层一层往下执行
  • 记录当前parent = old_parent
  • 走到最后的位置是hole_index
  • hole_index和它的now_parent是相同的值
  • push_heap原来的old_parent值到random_iter[old_parent : hole_index]
• 退一步(old_parent-1)，由底层到top,逐层一个一个执行上一步的步骤
• 执行到top停止

代码逻辑示例图：

直接swap交换的话逻辑会简单很多:

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 = 孩子节点的较大值
      __secondChild--;

    *(__first + __holeIndex) = *(__first + __secondChild);  // __secondChild的值赋值给父节点__holeIndex
    __holeIndex = __secondChild;
    __secondChild = 2 * (__secondChild + 1);
  }

  if (__secondChild == __len) {     // 碰到了最后的元素，也就是原来的堆顶元素
    *(__first + __holeIndex) = *(__first + (__secondChild - 1));
    __holeIndex = __secondChild - 1;
  }
  __push_heap(__first, __holeIndex, __topIndex, __value);   // push原来的最后那个元素
}

template <class _RandomAccessIterator, class _Tp, class _Distance>
void 
__make_heap(_RandomAccessIterator __first,
            _RandomAccessIterator __last, _Tp*, _Distance*)
{
  if (__last - __first < 2) return; // 只有一个元素
  _Distance __len = __last - __first; // 元素个数
  _Distance __parent = (__len - 2)/2; // 最后一个节点的父节点的距离
    
  while (true) {
    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
    if (__parent == 0) return;
    __parent--;
  }
}

template <class _RandomAccessIterator>
inline void 
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
  __make_heap(__first, __last,
              __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
}

time complexity

时间复杂度

建堆	插入	删除	排序
O(n)	O(logn)	O(logn)	O(nlogn)

总结

• 原地排序算法依赖于有序容器，快排也是原地排序(有序容器)
• 不稳定的排序，和快排一样
• 不是顺序访问，对cpu缓存不友好，这一点不如quicksort
• 数据交换次数多于快排