ARTICLE DETAIL

建站实战干货

来自一线的建站与推广经验沉淀，每一条都经过真实交付验证。

首页 / 资讯中心 / 正文

【2014-07-15】C++ STL读书笔记：stl_heap.h

2026/9/4 16:47:48 拓冰建站 浏览量
【2014-07-15】C++ STL读书笔记：stl_heap.h [历史归档]本文原发布于 cstriker1407.info 个人博客内容为历史存档仅供参考。发布时间2014-07-15 标题C STL读书笔记stl_heap.h分类编程 / C C / C STL 标签CC·stl·heapC STL读书笔记stl_heap.h备注stl\_heap.h:push\_heap:pop\_heap:make\_heap:sort\_heap:备注本读书笔记基于侯捷先生的《STL源码剖析》截图和注释版权均属于原作者所有。本读书笔记中的源码部分直接拷贝自SGI-STL部分代码删除了头部的版权注释但代码版权属于原作者。小弟初看stl很多代码都不是太懂注释可能有很多错误还请路过的各位大牛多多给予指导。为了降低学习难度作者这里换到了SGI-STL-2.91.57的源码来学习代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】根据侯捷先生所著《STL源码剖析》可知STL中的heap本质上是一棵最大完全二叉树。1 整个树除了最底层的节点外其余各层都是填满的。最底层如果不满则从左至右是没有空隙的。2 每个节点值都大于等于其子节点值。stl_heap.h:push_heap://插入一个元素到最大完全二叉树中。//first:最大完全二叉树的根节点的iterator值。//holeIndex要插入的完全二叉树的节点的编号即当前空闲节点编号。//topindex要插入的值在二叉树中的最小的节点编号//value要插入的值。templateclassRandomAccessIterator,classDistance,classTvoid__push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value){Distance parent(holeIndex-1)/2;//首先根据当前空闲节点编号算出其父节点编号。while(holeIndextopIndex*(firstparent)value){//如果要插入的值父节点的值就把父节点和当前节点互换然后继续循环比较。*(firstholeIndex)*(firstparent);holeIndexparent;parent(holeIndex-1)/2;}//循环结束之后将value放入找到的节点里。*(firstholeIndex)value;}如下图加入要把80插入当前的二叉树中那么80首先会找到其父节点50由于8050,那么就将50放到之前要插入80的位置然后把80的插入位置更新为50所在的节点再次循环比较。找到80当前插入位置的父节点即60,8060。同样将60和80的位置互换。再次循环比较找到80插入位置的父节点90,8090.无需位置互换。此时80的插入位置已经找到了。就将80插入即可。//整理成最大完全二叉树。//这里提供两个iterator分别指向存储树的数据结构的起始最后位置。//这里吧数据结构的最后一个节点插入二叉树中。//这里的意思是该数据结构中除了最后一个元素外其他的元素都符合最大完全二叉树。这里最后一个元素是刚刚插入的需要整理一下才能让整个数据结构符合最大完全二叉树。//比如数组【90,70,60,50,50,50,55,40,30,20,10,80】如上图所示。除了最后一个元素80外其他的元素都符合最大完全二叉树。//这里first指向90,last指向80之后的下一个元素。last-1指向80templateclassRandomAccessIterator,classDistance,classTinlinevoid__push_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*){__push_heap(first,Distance((last-first)-1),Distance(0),T(*(last-1)));}//整理成最大完全二叉树。templateclassRandomAccessIteratorinlinevoidpush_heap(RandomAccessIterator first,RandomAccessIterator last){__push_heap_aux(first,last,distance_type(first),value_type(first));}//和上面的代码一样只不过是添加了自定义比较函数templateclassRandomAccessIterator,classDistance,classT,classComparevoid__push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value,Compare comp){Distance parent(holeIndex-1)/2;while(holeIndextopIndexcomp(*(firstparent),value)){*(firstholeIndex)*(firstparent);holeIndexparent;parent(holeIndex-1)/2;}*(firstholeIndex)value;}//和上面的代码一样只不过是添加了自定义比较函数templateclassRandomAccessIterator,classCompare,classDistance,classTinlinevoid__push_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Compare comp,Distance*,T*){__push_heap(first,Distance((last-first)-1),Distance(0),T(*(last-1)),comp);}//和上面的代码一样只不过是添加了自定义比较函数templateclassRandomAccessIterator,classCompareinlinevoidpush_heap(RandomAccessIterator first,RandomAccessIterator last,Compare comp){__push_heap_aux(first,last,comp,distance_type(first),value_type(first));}pop_heap://从上到下调整二叉树。当二叉树被删掉了某个父节点后重新从子节点中找到最大值。//需要调整下才可以恢复成最大完全二叉树。//first:最大完全二叉树的根节点的iterator值。//holeIndex:要调整的二叉树的根节点一般来讲该根节点不符合二叉树的要求//len二叉树调整的最大范围。templateclassRandomAccessIterator,classDistance,classTvoid__adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T value){Distance topIndexholeIndex;Distance secondChild2*holeIndex2;//首先找到右子节点while(secondChildlen){if(*(firstsecondChild)*(first(secondChild-1)))//在两个子节点中找到一个比较大的节点secondChild--;*(firstholeIndex)*(firstsecondChild);//然后把父节点和较大子节点互换holeIndexsecondChild;//然后继续循环比较。secondChild2*(secondChild1);}//特殊情况处理如果比较到最后发现最后的右子节点就是最开始换过的节点那么就不在比较直接和左子结点互换。//因为这里最后面的那个节点会被删掉所以不用关心。//个人感觉先和左子节点比较下更好虽然下面有__push_heap。if(secondChildlen){*(firstholeIndex)*(first(secondChild-1));holeIndexsecondChild-1;//这里的holeIndex向前进了一格因此后面的__push_heap会跳过最后一格。}//将调整后的树调用__push_heap如果是pop_heap那么基本上没有作用如果是make_heap可以将原来的元素重新入树。__push_heap(first,holeIndex,topIndex,value);}如下图这里加入我们要删除90那么我们就把90和最后的一个元素30互换这样30成了根节点。为了让新的二叉树符合要求这里就把30和其子节点中的较大值80比较3080互换后继续比较新的子节点的较大值为60,3060继续互换比较后循环但是这里就进入了特殊情况30的右子节点就是最后的节点90这样便不会比较会退出循环然后直接和50互换。最后调用push_heap重新检查一下。//弹出树顶节点。调用__adjust_heap。templateclassRandomAccessIterator,classT,classDistanceinlinevoid__pop_heap(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result,T value,Distance*){*result*first;//首先获取到根节点值。__adjust_heap(first,Distance(0),Distance(last-first),value);}templateclassRandomAccessIterator,classTinlinevoid__pop_heap_aux(RandomAccessIterator first,RandomAccessIterator last,T*){//注意这里的last均减1传入这样最后的那个元素在__push_heap时便会被略掉。__pop_heap(first,last-1,last-1,T(*(last-1)),distance_type(first));}templateclassRandomAccessIteratorinlinevoidpop_heap(RandomAccessIterator first,RandomAccessIterator last){__pop_heap_aux(first,last,value_type(first));}//和上面的代码一样只不过是添加了自定义比较函数templateclassRandomAccessIterator,classDistance,classT,classComparevoid__adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T value,Compare comp){Distance topIndexholeIndex;Distance secondChild2*holeIndex2;while(secondChildlen){if(comp(*(firstsecondChild),*(first(secondChild-1))))secondChild--;*(firstholeIndex)*(firstsecondChild);holeIndexsecondChild;secondChild2*(secondChild1);}if(secondChildlen){*(firstholeIndex)*(first(secondChild-1));holeIndexsecondChild-1;}__push_heap(first,holeIndex,topIndex,value,comp);}templateclassRandomAccessIterator,classT,classCompare,classDistanceinlinevoid__pop_heap(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result,T value,Compare comp,Distance*){*result*first;__adjust_heap(first,Distance(0),Distance(last-first),value,comp);}templateclassRandomAccessIterator,classT,classCompareinlinevoid__pop_heap_aux(RandomAccessIterator first,RandomAccessIterator last,T*,Compare comp){__pop_heap(first,last-1,last-1,T(*(last-1)),comp,distance_type(first));}templateclassRandomAccessIterator,classCompareinlinevoidpop_heap(RandomAccessIterator first,RandomAccessIterator last,Compare comp){__pop_heap_aux(first,last,value_type(first),comp);}make_heap://构造一个最大完全二叉树templateclassRandomAccessIterator,classT,classDistancevoid__make_heap(RandomAccessIterator first,RandomAccessIterator last,T*,Distance*){if(last-first2)return;Distance lenlast-first;Distance parent(len-2)/2;//最下边最右边的最小子树的根节点。while(true){//注意这里第4个参数是T(*(first parent))即将弹出的元素再插入。这样树的元素保持不变//但是会变为最大二叉树。__adjust_heap(first,parent,len,T(*(firstparent)));if(parent0)return;parent--;}}//构造一个最大完全二叉树templateclassRandomAccessIteratorinlinevoidmake_heap(RandomAccessIterator first,RandomAccessIterator last){__make_heap(first,last,value_type(first),distance_type(first));}templateclassRandomAccessIterator,classCompare,classT,classDistancevoid__make_heap(RandomAccessIterator first,RandomAccessIterator last,Compare comp,T*,Distance*){if(last-first2)return;Distance lenlast-first;Distance parent(len-2)/2;while(true){__adjust_heap(first,parent,len,T(*(firstparent)),comp);if(parent0)return;parent--;}}//构造一个最大完全二叉树使用自定义比较templateclassRandomAccessIterator,classCompareinlinevoidmake_heap(RandomAccessIterator first,RandomAccessIterator last,Compare comp){__make_heap(first,last,comp,value_type(first),distance_type(first));}如下图所示parent的值为最下最右子树的根节点通过不断递减便会由右至左有下至上不断的对子树进行排序当parent为0时说明已经排序到了根节点树就完成了。sort_heap://通过不停的弹出最大元素生成一个递增序列。templateclassRandomAccessIteratorvoidsort_heap(RandomAccessIterator first,RandomAccessIterator last){while(last-first1)pop_heap(first,last--);}templateclassRandomAccessIterator,classComparevoidsort_heap(RandomAccessIterator first,RandomAccessIterator last,Compare comp){while(last-first1)pop_heap(first,last--,comp);}