现在的位置: 首页 > 综合 > 正文

STL源码剖析 – 第4章 序列式容器 – heap

2019年07月18日 ⁄ 综合 ⁄ 共 10821字 ⁄ 字号 小 中 大 ⁄ 评论关闭

4.7.1 heap概述

    在STL中，heap并不是一种容器，而是一种算法，作为下一节的priority queue的助手，任何能够提供随机访问迭代器的容器都能支持heap的操作。heap不需要遍历内容，所以没有属于自己的迭代器。本文介绍的heap是基于vector容器的操作；有关堆的定义可以参考：http://blog.csdn.net/u012243115/article/details/40474527。本文介绍的源码出自SGISTL中<stl_heap.h>文件。堆的结构如下图所示：

4.7.2 heap算法

对堆的操作主要包括：

1、  push_heap（在堆尾插入元素并维护堆的性质）

2、  pop_heap（删除堆顶（最大值），并维护堆的性质）

3、  sort_heap（对堆进行排序，每次循环把堆顶放到最后（从小到大））

4、  make_heap（建堆，即把一个无序的数组转化成最大堆）

push_heap的操作如下图所示：

pop_heap的操作如下图所示：

4.7.3 heap没有迭代器

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

4.7.4 heap源码剖析

由于前面介绍过最大堆和最小堆的思想与实现步骤，这里不介绍了，直接进行源码剖析：

//在STL中，heap不作为容器，只是提供了关于Heap操作的算法。  
//heap没有自己的迭代器，只要支持RandomAccessIterator的容器都可以作为Heap容器  
#ifndef __SGI_STL_INTERNAL_HEAP_H  
#define __SGI_STL_INTERNAL_HEAP_H  
  
__STL_BEGIN_NAMESPACE  
  
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)  
#pragma set woff 1209  
#endif  
  
// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.  
  
//堆中添加元素；关于push_heap操作的原型有两个  
//注意: push_heap()操作之前必须保证新添加的元素已经加入到容器末尾  
//***************************************************************  
//*     第一个版本使用operator<操作  
//*     template< class RandomIt >  
//*     void push_heap( RandomIt first, RandomIt last );  
//***************************************************************  
//*     第二个版本使用比较函数comp  
//*     template< class RandomIt, class Compare >  
//*     void push_heap( RandomIt first, RandomIt last,Compare comp );  
//***************************************************************  
//* 比较函数comp：comparison function which returns ​true if the first argument is less than the second.   
//* The signature of the comparison function should be equivalent to the following:  
//*     bool cmp(const Type1 &a, const Type2 &b);  
//***************************************************************  
template <class _RandomAccessIterator, class _Distance, class _Tp>  
void   
__push_heap(_RandomAccessIterator __first,  
            _Distance __holeIndex, _Distance __topIndex, _Tp __value)  
{//当前节点标号为__holeIndex- 1即为新插入元素标号，因为根节点标号是从0开始，所以这里要-1  
  _Distance __parent = (__holeIndex - 1) / 2;//找出当前节点的父节点  
  //尚未达到根节点,且所插入数据value大于父节点的关键字值    
  while (__holeIndex > __topIndex && *(__first + __parent) < __value) {  
    *(__first + __holeIndex) = *(__first + __parent);//交换当前节点元素与其父节点元素的值  
    __holeIndex = __parent;//更新当前节点标号，上溯  
    __parent = (__holeIndex - 1) / 2;//更新父节点  
  }   //持续达到根节点，或满足heap的性质  
  *(__first + __holeIndex) = __value;//插入正确的位置  
}  
  
template <class _RandomAccessIterator, class _Distance, class _Tp>  
inline void   
__push_heap_aux(_RandomAccessIterator __first,  
                _RandomAccessIterator __last, _Distance*, _Tp*)  
{  
    //__last - __first) - 1表示插入后元素的个数，也是容器的最后一个下标数字  
    //新插入的元素必须位于容器的末尾  
    __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),   
              _Tp(*(__last - 1)));  
}  
  
//第一个版本push_heap默认是operator<操作  
template <class _RandomAccessIterator>  
inline void   
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)  
{  
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);  
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,  
                 _LessThanComparable);  
  __push_heap_aux(__first, __last,  
                  __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));  
}  
  
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)) {  
    *(__first + __holeIndex) = *(__first + __parent);  
    __holeIndex = __parent;  
    __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);  
}  
//第二个版本push_heap自定义比较操作函数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()操作, 执行完操作后要自己将容器尾元素弹出  
//default (1):    
//          template <class RandomAccessIterator>  
//          void pop_heap (RandomAccessIterator first, RandomAccessIterator last);  
//custom (2):     
//          template <class RandomAccessIterator, class Compare>  
//          void pop_heap (RandomAccessIterator first, RandomAccessIterator last,  
//                 Compare comp);  
//***********************************************************************  
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));  
}  
  
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) {  
    if (__comp(*(__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, __comp);  
}  
  
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;  
  __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)  
{  
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);  
  __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);  
}  
  
  
//创建堆  
//default(1):     
//          template <class RandomAccessIterator>  
//          void make_heap (RandomAccessIterator first, RandomAccessIterator last);  
//custom (2):     
//          template <class RandomAccessIterator, class Compare>  
//          void make_heap (RandomAccessIterator first, RandomAccessIterator last,Compare comp );  
  //********************************************************************************  
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)  
{  
  __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, class _Compare,  
          class _Tp, class _Distance>  
void  
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,  
            _Compare __comp, _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)),  
                  __comp);  
    if (__parent == 0) return;  
    __parent--;  
  }  
}  
  
template <class _RandomAccessIterator, class _Compare>  
inline void   
make_heap(_RandomAccessIterator __first,   
          _RandomAccessIterator __last, _Compare __comp)  
{  
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);  
  __make_heap(__first, __last, __comp,  
              __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));  
}  
  
//排序堆里面的内容  
//default(1):     
//          template <class RandomAccessIterator>  
//          void sort_heap (RandomAccessIterator first, RandomAccessIterator last);  
//custom (2):     
//          template <class RandomAccessIterator, class Compare>  
//          void sort_heap (RandomAccessIterator first, RandomAccessIterator last,  
//                        Compare comp);  
//**************************************************************************  
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--);//每次取出根节点元素，直到heap为空  
}  
  
template <class _RandomAccessIterator, class _Compare>  
void   
sort_heap(_RandomAccessIterator __first,  
          _RandomAccessIterator __last, _Compare __comp)  
{  
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);  
  while (__last - __first > 1)  
    pop_heap(__first, __last--, __comp);  
}  
  
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)  
#pragma reset woff 1209  
#endif  
  
__STL_END_NAMESPACE  
  
#endif /* __SGI_STL_INTERNAL_HEAP_H */  
  
// Local Variables:  
// mode:C++  
// End:

    举例说明heap的操作：

#include <iostream>     // std::cout  
#include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap  
#include <vector>       // std::vector  
  
int main () {  
  int myints[] = {10,20,30,5,15};  
  std::vector<int> v(myints,myints+5);  
  
  std::make_heap (v.begin(),v.end());  
  std::cout << "initial max heap   : " << v.front() << '\n';  
  
  std::pop_heap (v.begin(),v.end()); v.pop_back();  
  std::cout << "max heap after pop : " << v.front() << '\n';  
  
  v.push_back(99); std::push_heap (v.begin(),v.end());  
  std::cout << "max heap after push: " << v.front() << '\n';  
  
  std::sort_heap (v.begin(),v.end());  
  
  std::cout << "final sorted range :";  
  for (unsigned i=0; i<v.size(); i++)  
    std::cout << ' ' << v[i];  
  
  std::cout << '\n';  
  
  return 0;  
}

输出：

initial max heap   : 30  
max heap after pop : 20  
max heap after push: 99  
final sorted range : 5 10 15 20 99

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞