本文章内容来源于《STL源码分析》第四章
- heap不归属于STL容器组件,扮演priority-quque的助手,即priority queue的底层;
1 概述
1.1 binary heap
- 一种 complete binary tree (完全二叉树)的存储方式
- 使用vector作为存储空间
1.2 heap的隐式表述法(implicit representation)
- 将数组的#0元素保留
- 那么在数组中,位于数组i处的节点的左子节点为2i,右子节点为(2*i +1)
-【SGI STL 并未使用这个方法】
1.3 max-heap
- STL实现的是大根堆
2 heap算法
2.1 push_heap 算法
- 新加入的元素位于最下一层作为叶节点,也就是插入到vector的end()处;
- 通过和父节点进行比较,如果值比父节点大,就父子对换位置,一直上溯,直到不需要对换或者到根节点为止;
- push_heap
// push_heap
template<class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last){
// 此函数调用的时候 新元素已经置于容器底部
__push_heap_aux(first,last,distance_type(first),value_type(first));
}
- 使用push_heap_aux 和 push_heap作为内部函数;
template<class RandomAccessIterator, class Distance, class T>
inline void __push_heap_aux(RandomAccessIterator first,
RandomAccessIterator last, Distance*, T*){
// 新值在容器最尾端,位置: (last -first)-1
// 隐式表述法 ,根节点编号从0开始
__push_heap(first, Distance(last - first)-1, Distance(0), T(*(last -1)));
}
// 一下这组push_back()不允许指定'大小比较标准'
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){ // 大根堆调整
// 尚未到达顶端并且父节点小于新值
*(first + holeIndex) = *(first + parent); // 令洞位置为父节点
holeIndex = parent; // 调整洞号, 向上提升
parent = (holeIndex - 1) /2; // 新父节点
} // 调整完成
*(first + holeIndex) = value; // 赋值
}
2.2 pop_heap算法
- 先将根节点和最下一层的最右边的叶节点对换位置;然后调整除了最后一个节点的vector的first,last-1]的堆;
- pop_heap
/**
pop_heap
1. 取走根节点
2. 满足完全二叉树的条件,将最下一层的最右边的叶节点拿掉
*/
template<class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last){
__pop_heap_aux(first, last, value_type(first));
}
- 使用了__pop_heap_aux作为内部函数:
// 根据隐式表述法, pop操作的结果为底部容器的第一个元素
// 首先将首值和尾节点互换,然后重新调整[first, last -1)
template<class RandomAccessIterator , class T>
inline void __pop_heap_aux(RandomAccessIterator first, RandomAccessIterator last,
T*){
__pop_heap(first,last-1, last-1, T(*(last - 1), distance_type(first));
}
template<class RandomAccessIterator, class T, class Distance>
inline void __pop_heap(RandomAccessIterator first,
RandomAccessIterator last,
RandomAccessIterator result,
T value, Distance*)
{
*result = * first; // 设定尾值为首值
//然后后面可以由容器pop_back()取出
// 重新调整heap
__adjust_heap(first,Distance(0), Distance(last -first), value);
}
- heap的调整算法:
__adjust_heap
`
template
void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
Distance len, T 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;
}
// 将要调整的洞号填入目前的洞号,
// 此时已经满足次序性
// 可直接为*(first + holeIndex) = value;
__push_heap(first, holeIndex, topIndex,value);
}
## 2.3 sort_heap 算法
- pop_heap每次将最大元素放到尾端,那么通过持续调用pop_heap算法就可以得到逆序序列;
/**
sort_heap
1. pop_heap 每次取出一个最大值,持续pop,可得逆序序列;
*/
template
void sort_heap(RandomAccessIterator first,
RandomAccessIterator last){
// 没执行一次pop_heap(),极值放在尾端
while(last - first >1){
pop_heap(first,last–); // 执行一次,操作范围缩小一点
}
}
## 2.4 make_heap算法
- 将一段现有数据转化一个heap
/*
make_heap: 将一段数据转化为堆
/
template
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last){
__make_heap(first,last, value_type(first),distance_type(first));
}
template
void __make_heap(RandomAccessIterator first,
RandomAccessIterator last, T, Distance)
{
if(last - first < 2) return ; // 长度0或1 不用重新排列
Distance len = last - first;
// 找出第一个需要重新排列的子树头部,以parent标出,
Distance parent = (len -2 ) /2;
while(true){
// 重新排列parent为首的子树,len为了让__adjust_heap()判断操作范围
__adjust_heap(first,parent,len,T(*(first+parent)));
if(parent == 0) return ; // 走完根节点就结束;
parent --; // 重排子树的头部向前一个节点;
}
}`