本文假设你已对堆排序的算法有主要的了解。 要分析 stl 中 heap 的源代码的独到之处。最好的办法就是拿普通的代码进行比較。话不多说,先看一段普通的堆排序的代码:
- //调整大顶堆。使得结构合理void max_heap(inta[],intnode,int size)
- {intlg=node;intl=node*2;intr=node*2+1;if(l<=size&&a[lg]if(r<=size&&a[lg]if(lg!=node)
- {//a[lg]=a[lg]^a[node];//交换
- //a[node]=a[lg]^a[node];
- //a[lg]=a[lg]^a[node];
- inttt=a[lg];
- a[lg]=a[node];
- a[node]=tt;
- max_heap(a,lg,size);
- }
- }//生成一个大顶堆void make_heap(inta[],int size)
- {for(inti=size/2;i>0;i--)
- {
- max_heap(a,i,size);
- }
- }//堆排序,使数据在数组中按从小到大的顺序排列void heap_sort(inta[],int size)
- {
- make_heap(a,size);for(inti=1;i<size;i++)
- {inttt=a[1];
- a[1]=a[size-i+1];
- a[size-i+1]=tt;
- max_heap(a,1,size-i);
- }
- }
相应第一个函数 max_heap(),stl 中有一个功能相似的函数 adjust_heap(),也是调整整个 heap,使之符合大顶堆的要求,代码例如以下:
- // ============================================================================
- // 保持堆的性质
- //整个的过程是从根节点開始,将根节点和其子节点中的最大值对调,一直到叶节点为止(称之为下溯)
- //然后。再从这个根节点開始。把它与其父节点进行比較,假设比父节点大,则父子节点对调。直到根节点为止(称之为上溯)
- //============================================================================
- // first 起始位置
- // holeIndex 要进行调整操作的位置
- // len 长度
- // value holeIndex新设置的值
- 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) {// 假设右孩子节点的值比左孩子节点的值要小。那么secondChild指向左孩子
- 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;
- }// 针对节点topIndex调用push_heap操作__push_heap(__first, __holeIndex, __topIndex, __value);
- }//上溯__push_heap(_RandomAccessIterator __first,
- _Distance __holeIndex, _Distance __topIndex, _Tp __value)
- {// 获取父节点的索引值_Distance __parent = (__holeIndex -1) /2;// 假设还没有上升到根节点,且父节点的值小于待插入节点的值
- while(__holeIndex > __topIndex && *(__first + __parent) < __value) {// 父节点下降到holeIndex*(__first + __holeIndex) = *(__first + __parent);// 继续往上检查__holeIndex = __parent;
- __parent = (__holeIndex -1) /2;
- }// 插入节点*(__first + __holeIndex) = __value;
- }
stl 里算法的堆的调整的主要流程如凝视里所说,主要是先进行下溯。直到叶节点,然后用 push_heap 进行上溯才调增完毕。对照之前的普通代码,主要有 3 点改变:
通过上述的分析,事实上我们也能够以小见大。
事实上 stl 中,存在着大量这种优化,递归转循环,降低边界检查,用赋值取代交换等等。假设我们能细致研究,并在平时的编码中也养成这种习惯,就能极大得提升代码的效率。
来源: http://www.bubuko.com/infodetail-2121800.html