STL源码笔记（14）—堆和优先级队列（一）

短命女 2022-08-21 14:59 147阅读 0赞

# STL源码笔记（14）—堆和优先级队列 #

priority\_queue是拥有权值观念的queue，跟queue类似，其只能在一端push，一端pop，不同的是，每次push元素之后再容器内部元素将按照一定次序排列，使得pop得到的元素始终是当前权值的极大值。

很显然，满足这个条件就需要某些机制了，缺省情况下使用max-heap大顶堆来实现，联想堆排序的实现，使用大顶完成序列从小到大的排序，过程大概是：

1.  把堆的根元素（堆中极大值）交换到最后
2.  堆的长度减1

这样每次取出堆中的极大值完成排序，刚好与优先级队列要求的权值最高类似，因此可以利用这个特性完成优先级队列。

对于一个优先级队列来说，他使用`vector<T>`作为其底层默认容器，与stack，queue类似，priority\_queue也是一个adapter(配接器)，被归类为`container adapter`

**注：**在SGI STL源码中priority\_queue的源码位于文件stl\_queue.h中，heap算法的源码位于stl\_heap.h中。

## heap算法 ##

heap算法是实现优先级队列的核心。主要有：

> 1.push\_heap()  
> 2.pop\_heap()  
> 3.\_\_adjust\_heap()  
> 4.sort\_heap()  
> 5.make\_heap()

除了\_\_adjust\_heap()外，其余四个都是可以在外部使用的函数，如果要实现堆排序的话可以直接使用上述4,5函数。

### push\_heap函数 ###

书中给了一个很形象的表述叫做percolate up(上溯)操作，这里假设：  
在容器vector中，前n个元素(索引0~n-1)为已经排好的max-heap，现在待插入元素的索引为n，这里，程序会在这里挖个坑，称之为`holeindex`，可以理解为我现在要插入一个元素，但是我并不知道要插在哪里，所以我先挖一个坑，然后经过一系列的算法，这个`holeindex`，要开始慢慢往上爬，以满足大顶堆条件，其实这里的上爬做了两件事：

1.  将比value小的parent节点往下拉
2.  将原来的holeindex往上拉，占据原来parent所在的位置

持续操作，直到holeindex爬到顶端（根节点），以及满足大顶堆的条件了，此时holeindex已经上溯到正确的位置，只需要将value值填进去即可。

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;//父节点位置
      while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
       //__comp默认是小于：父节点小于子节点
      //调整hole的位置，如果满足条件hole将一直上溯
        *(__first + __holeIndex) = *(__first + __parent);
        __holeIndex = __parent;
        __parent = (__holeIndex - 1) / 2;
      }
      *(__first + __holeIndex) = __value;//把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
      __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
                  _Tp(*(__last - 1)), __comp);
    }
    
    template <class _RandomAccessIterator, class _Compare>
    inline void 
    push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
              _Compare __comp)
    {
      __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
      __push_heap_aux(__first, __last, __comp,
                      __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
    }

### pop\_heap与\_\_adjust\_heap函数 ###

与push\_heap对应的就是“出堆”操作了，在堆排序中，我们对已经建好的堆进行“出堆”，操作是每次将堆顶根元素换到容器末尾，先对堆的长度减1，再对堆进行调堆操作，重复进行直到堆中所有元素出来，由于出堆操作每次出的是堆顶元素，也就是极大值，因此完成出堆操作后就完成排序工作。

pop\_heap与push\_heap对应的是percolate down(下溯)操作，这里很容易理解因此堆顶的根元素被取走以后，这里原来的根元素就是一个没有元素的空节点了，也就是所谓的holeindex，这里就是要将这个holeindex调整到合适的位置，holeindex之前的元素是一个堆，实际上做的工作是：

1.  找到holeindex对应两个孩子中较大的将其换到holeindex的位置
2.  将holeindex下溯到上述较大孩子的索引的位子
3.  重复执行上述操作，最终holeindex将落在某个叶子节点处。

上述第2点需要考虑没有右子树的情况，例如：

![这里写图片描述][20160506121316603]  
当下溯到（索引2处）原65节点时，此时没有右节点，右节点索引second==len

由于此时并没有考虑从容器末尾换出来的value值，所以要对堆的索引为 0~holeindex（模拟一下过程可以很容易得到此时的holeindex位于叶子节点处） 的元素进行一次push\_heap操作，使得value插入到合适的位置。

所以说，pop\_heap的工作实际上很简单，主要任务是极大值出堆后要对剩余的元素进行重新调整，使得其成一个堆。

//4.
    template <class _RandomAccessIterator, class _Distance, class _Tp>
    void 
    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
                  _Distance __len, _Tp __value)
    {
      _Distance __topIndex = __holeIndex;//holeindex在顶端
      _Distance __secondChild = 2 * __holeIndex + 2;//从右孩子开始
      while (__secondChild < __len) {
       //表示holeindex还没有到叶子节点，要不停下溯
      //取左右孩子的最大值
        if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
          __secondChild--;
        *(__first + __holeIndex) = *(__first + __secondChild);//较大的孩子上调
        __holeIndex = __secondChild;//holeindex下溯
        __secondChild = 2 * (__secondChild + 1);
      }
      if (__secondChild == __len) {
       //当前holeindex只有左孩子
        *(__first + __holeIndex) = *(__first + (__secondChild - 1));
        __holeIndex = __secondChild - 1;
      }
      __push_heap(__first, __holeIndex, __topIndex, __value);//重新插入
    }
    
    //3.
    template <class _RandomAccessIterator, class _Tp, class _Distance>
    inline void 
    __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
               _RandomAccessIterator __result, _Tp __value, _Distance*)
    {
      *__result = *__first;//首先将堆中极大值赋给堆末尾位置
      //这里的last已经完成减1操作
      //调堆操作
      __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
    }
    
    //2.
    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));
    }
    
    //1.
    template <class _RandomAccessIterator>
    inline void pop_heap(_RandomAccessIterator __first, 
                         _RandomAccessIterator __last)
    {
      __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
      __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
                     _LessThanComparable);
      __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));//直接调用
    }

### make\_heap和heap\_sort ###

这两个函数实现了堆排序。  
make\_heap是将一段现有的数据转化成一个heap，操作就是，从第一个非叶子节点向前进行调堆操作，为什么要选择第最后一个非叶子节点呢？因为，调堆操作是对holeindex进行下溯，现在你都是叶子节点了还怎么下？  
至于最后一个非叶子节点的计算公式：  
index=(len−2)/2(1)  
其中len是数组的长度。

heap\_sort函数就简单了，不断的执行pop\_heap操作即可：

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;
       //找出第一个需要重排的子树头部（因为需要执行perlocate down操作，而叶子节点不需要执行该操作）
      _Distance __parent = (__len - 2)/2;
    
      while (true) {
        __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
        if (__parent == 0) return;
        __parent--;
      }
    }
    
    //将一段现有的数据转化成一个heap...在堆排序中就是build_heap
    template <class _RandomAccessIterator>
    inline void 
    make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
      __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
                     _LessThanComparable);
      __make_heap(__first, __last,
                  __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
    }

//每次将一个极大值放到尾端
    template <class _RandomAccessIterator>
    void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
      __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
                     _LessThanComparable);
      while (__last - __first > 1)
        pop_heap(__first, __last--);
    }

[20160506121316603]: /images/20220724/692158c4025d403b844ed4be05280f66.png