【STL源码剖析】第四章 序列式容器 之 heap和priority_queue底层实现

时间:2022-09-25 04:18:28

heap

heap概述

heap并不归属于STL容器组件,它扮演priority queue的助手。binary max heap是priority queue的底层机制。

binary heap是一种complete binary tree(完全二叉树),也就是说,整棵binary tree除了最底层的叶节点(s)之外,是填满的,而最底层的叶节点(s)由左至右不得由空隙。

【STL源码剖析】第四章 序列式容器 之 heap和priority_queue底层实现

complete binary tree整棵树内没有任何节点漏洞。利用array来存储completebinary tree的所有节点,将array的#0元素保留,那么当complete binary tree的某个节点位于array的i处时,其左子节点必位于array的2i处,右子节点必位于array的2i+1处,父节点必位于i/2处。

根据元素排列方式,heap分为max-heap和min-heap两种,前者每个节点的键值都大于或等于其子节点的值,后者每个节点的键值都小于或等于其子节点的值。max-heap中最大值在根节点,min-heap最小值在根节点。底层存储结构为vector或者array。

heap算法

push_heap算法

为了满足complete binary tree的条件,新加入的元素一定要放在最下一层作为叶节点,并填补在由左至右的第一个空格,也就是吧新元素插入在底层vector的end()处。

【STL源码剖析】第四章 序列式容器 之 heap和priority_queue底层实现

新元素是否适合于其现有位置呢?为满足max-heap的条件(每个节点的键值都大于或等于其子节点键值),我们执行一个所谓的percolate up(上溯)程序:将新节点拿来与其父节点比较,如果其键值(key)比父节点大,就父子对换位置,如此一直上溯,直到不需对换或直到根节点为止。

  
  template<class RandomAccessIterator>
  inline void push_heap(RandomAccessIterator first,RandomAccessIterator last)
  {
      //注意,此函数被调用时,新元素应已置于底部容器的最尾端
      _push_heap_aux(first,last,distance_type(first),value_type(first))
  }
  
  template<class RandomAccessIterator,class Distance,class T>
  inline void _push_heap_aux(RandomAccessIterator first,Distance*,T*)
  {
      _push_heap(first,Distance(last-first)-1),Distance(0),T(*(last-1)));
      //以上系根据implicit representation heap的结构特性:新值必须置于底部容器的最尾端,此即第一个洞号:(last-first)-1
  }
  
  template<class RandomAccessIterator,class Distance,class T>
  void _push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value){
      Distance parent(holeIndex-1)/2;//找出父节点
      while(holeIndex>topIndex&&*(first+parent)<value)
      {
          //当尚未达到顶端,且父节点小于新值(于是不符合heap的次序特性)
          //由于以上使用operator<,可知STL heap是一种max-heap
          *(first+holeIndex)=*(first+parent);//令洞值为父值
          holeIndex=parent;//调整洞号,向上提升至父节点
          parent=(holeIndex-1)/2;//新洞的父节点
      } //持续至顶端,或满足heap的次序特性为止
      *(first+holeIndex)=value;//令洞值为新值,完成插入操作
  }
pop_heap算法

图示为pop_heap算法的实际操作情况。既然自身为max-heap,最大值必然在根节点。pop操作取走根节点(其实是移至底部容器vector的最后一个元素)之后,为了满足complete binary tree的条件,必须将最下一层右边的叶节点拿掉,现在我们的任务是为这个被拿掉的节点找一个适当的位置。

为满足max-heap的条件(每个节点的键值都大于或等于其子节点键值),我们执行一个所谓的percolate down(下溯)程序:将根节点(最大值被取走后,形成一个”洞“)填入上述那个失去生存空间的叶节点值,再将它拿来和其两个子节点比较键值(key),并于较大子节点对调位置。如此一直下放,直到这个”洞“的键值大于左右两个子节点,或直到下放至叶节点为止。

【STL源码剖析】第四章 序列式容器 之 heap和priority_queue底层实现

  
  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);  
  }  
    
  template <class _RandomAccessIterator, class _Tp, class _Distance>  
  inline void   
  __pop_heap(_RandomAccessIterator _first, _RandomAccessIterator _last,  
             _RandomAccessIterator _result, _Tp _value, _Distance*)  
  {  
    *_result = *_first;//把原始堆的根节点元素放在容器的末尾  
    //调整剩下的节点元素,使其成为新的heap  
    _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)  
  {  
    _STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);  
    _STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,  
                   _LessThanComparable);  
    _pop_heap_aux(_first, _last, _VALUE_TYPE(_first));  
  }
sort_heap算法

既然每次pop_heap可获得heap中键值最大的元素,如果持续对整个heap做pop_heap操作,每次将操作范围从后向前缩减一个元素(因为pop_heap会把键值最大的元素放在底部容器的最尾端),当整个程序执行完毕时,我们便有了一个递增序列。

  
  //以下这个sort_heap()不允许指定“大小比较标准”
  template <class RandomAccessIterator>
  void sort_heap(RandomAccessIterator first,RandomAccessIterator last){
   //以下,每没执行一次pop_heap(),极值(在STL heap中为极大值)即被放在尾端
   //扣除尾端再执行一次pop_heap(),次极值又被放在新尾端。一直下去,最后即得排序结果
   while(last-first>1)
    pop_heap(first,last--);
  }

【STL源码剖析】第四章 序列式容器 之 heap和priority_queue底层实现

【STL源码剖析】第四章 序列式容器 之 heap和priority_queue底层实现

make_heap算法

这个算法用来将一段现有数据转化成一个heap。

  
  //将[first,last)排列成一个heap
  template<class RandomAccessIterator>
  inline void make_heap(RandomAccessIterator first,RandomAccessIterator last){
   _make_heap(first,last,value_type(first),distance_type(first));
  }
  //以下这组make_heap()不允许指定“大小比较标准”
  template<class RandomAccessIterator,class T,class Distance>
  void _make_heap(RandomAccessIterator first,RandomAccessIterator last,T*,Distance*){
   if(last-first<2) return;//如果长度为0或1,不必重新排列
   Distance len=last-first;
   //找出第一个需要重排的子树头部,以parent标示出。由于任何叶节点都不需执行parlocate down,所以有以下计算。
   Distance parent=(len-1)/2;
   
      while(true){
       //重排以parent为首的子树。len是为了让_adjust_heap()判断操作范围
       _adjust_heap(first,parent,len,T(*(first+parent)));
       if(parent==0) return;  //走完根节点,就结束
       parent--             //(即将重排子树的)头部向前一个节点
      }
  }
heap没有迭代器

heap的所有元素都必须遵循特别的(complete binary tree)排列规则,所以heap不提供遍历功能,也不提供迭代器。

priority_queue

priority_queue概述

priority_queue是一个拥有权值观念的queue,它允许加入新元素、移除就元素、审视元素值等功能。由于它是一个queue,所以只允许在低端加入元素,并从顶端取出元素,除此之外别无其他存取元素的途径。

priority_queue带有权值观念,其内的元素并非依照被推入的顺序排列,而是自动依照元素的权值排列(通常权值以实值标识)。权值最高者,排在最前面。

缺省情况下priority_queue系利用一个max-heap完成,后者是一个以vector表现的complete binary tree。max-heap可以满足priority_queue所需要的“依权值高低自动递增排序”的特性。

【STL源码剖析】第四章 序列式容器 之 heap和priority_queue底层实现

priority_queue缺省情况下是以vector为底层容器,再加上heap处理规则,STL priority_queue往往不被归类为container(容器),而被归类为containeradapter。

priority_queue测试实例

  
  #include<queue>  
  #include<iostream>  
  #include<algorithm>  
  using namespace std;  
    
  int main(void){  
      //test priority queue...  
      int ia[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };  
      priority_queue<int> ipq(ia, ia + 9);  
      cout << "size= " << ipq.size() << endl;    //size=9
    
      for (int i = 0; i < ipq.size(); ++i)  
          cout << ipq.top() << ' ';              //9 9 9 9 9 9 9 9 9
      cout << endl;  
    
      while (!ipq.empty()){  
          cout << ipq.top() << ' ';             //9 8 5 4 3 3 2 1 0
          ipq.pop();  
      }  
      cout << endl;  
    
      system("pause");  
      return 0;  
  }