走进STL - heap，小树芽
heap，可能听过的人不多，这篇主要留给我和有缘人看吧。
1、heap是什么
heap并不属于STL容器组件，它是个“幕后白手”，扮演priority queue的助手。
顾名思义，那个queue允许用户以任何次序插入数据，但是在插入的时候会根据优先级进行排序，以保证取出的时候是按照优先级排序的。
如果以List作为这个优先级队列的底层机制，那么排序将会很麻烦，如果以二叉搜索树的话，未免大材小用了。
而难度夹在中间的binary heap便是不二人选了。
所谓binary heap,就是一种完全二叉树，整棵树除了底层节点外，都是填满的，从左至右又不得又间隙。
苍白无力的文字啊，来看张图实在：
简单明了吧，可以用想象下面有一个数组来存储所有节点，以树根节点作为数组的[0]位置，可以发现，任何一个节点 [i] 的左子节点必位于 [2i] 处，其右子节点必位于 [2i+1] 处。
而任何一个节点 [k]，其父节点必位于 [k/2] 处。
通过这简单的规则，咱就种了一棵树，完全二叉树。
而这颗二叉树需要能动态的增加节点，所以采用vector作为这棵树的底层土壤是个理想的选择。
根据元素排列方式，heap可以分为max-heap和min-heap。STL供应的是max-heap,最大值在头结点。
2、heap算法
2.1 push_heap算法（尾端插入元素）
本来是自己画了图，但是理解了书中的图之后，发现他的图更有一番风味。
原先我也疑惑于为何同一级中左边的节点会比右边节点大，后来我想明白了。
在插入过程中，这个顺序被打乱是难以避免的，况且这个排序于取出数据并无影响，所以没必要在做额外工作对树的底层做那么精细的排序。
如果还是不理解，先看下去，慢慢的就会茅塞顿开。
在尾部插入时，总是将节点插入到最底层的最右节点，不管你要插入的数据右多大，见上图第一个步骤。
插入之后执行上溯操作，将新节点拿来与父节点进行比较，如果“青出于蓝胜于蓝”，那么将父子节点互换位置。见上图第二个步骤。
之后持续执行上一个步骤，直到不再互换位置。见上图三、四个步骤。
至于下面被打乱的顺序，不用担心，乱中有序。
正是由于这波操作，使得同一级会出现左边的节点比右边的大的情况。
下面来看一下算法的实现细节：
//该函数接受两个迭代器，用来表现一个heap底部容器的头尾，并且新元素已经插入到底部容器的最尾端。
template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first,RandomAccessIterator last)
{
__push_heap_aux(first,last,distance_type(first),value_type(first));/*这俩type在上一篇提到了，不知道也就算了吧，毕竟上一篇也不短*/
}
template <class RandomAccessIterator,class Distance,class T>
inline void __push_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{
__push_heap(first,Distance((last-first)-1),Distance(0),T(*(last - 1))); //(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) //尚未到达顶端，且父节点小于新值，这个循环将父值不断下调
{
*(first + holeIndex) = *(first + parent); //令新值为父
holeIndex = parent; //调节洞号，向上提升至父节点
parent = (holeIndex -1)/2; //新洞的父节点
}
*(first + holeIndex) = value; //令洞值为新值，完成插入操作
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
看下来，果然会茅舍顿开吧。
2.2 pop_heap算法（头部插入元素）
看完上面的插入，可能会有人觉得这样打乱顺序的话取出会有问题，其实会有吗？不知道，看下去。
还是用书上的图啊。
取出元素时，首先将1根节点拿下来，留下一个洞洞，见上图第一步到第二步。
还要将当前树的最后一个节点拿下来，并将根节点放到尾节点在容器中的位置。见上图步骤二。
接下来将尾节点和原根节点的两个子节点比较大小，将大的那个推上根节点。见上图步骤三。同样留下一个洞洞。
循环这个“向下流放”的过程，直到原尾结点插入树中或者到了最底层。见上图步骤四。
看懂了这个图之后我们来看算法的实现细节：
template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first,RandomAccessIterator last)
{
__pop_heap_aux(first,last,value_type(first));
}
template <class RandomAccessIterator,class T>
inline void __pop_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{
__pop_heap(first,last-1,last-1,T(*(last - 1)),diatance_type(first));
}
template <class RandomAccessIterator,class Distance,class T>
void __push_heap(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result,T value,Distance*)
{
*result = *first; //设定尾值为首值，客端稍后可以pop_back()将值取出
__adjust_heap(first,Distance(0),Distance(last - first),value);
}
template <class RandomAccessIterator,class Distance,class T>
void __adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T 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);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
2.3 sort_heap算法（思想简介）
不断对heap进行pop操作，便可达到排序效果。
这个图可以根据上面两张图自行脑补，算法也可以自行脑补。
2.4 heap迭代器
嘿嘿，那当然是没有迭代器了，所有元素都必须遵循特别的排列规则，又不提供遍历功能，要什么迭代器。
2.5 make_heap （制造heap）
这个算法就是用来将现有的一段数据转化成一个heap。
思想不多说，直接看代码：
template<class RandomAccessIterator>
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first,RandomAccessIterator last)
{
__make_heap(first,last,distance_type(first),value_type(first));
}
//不允许指定比较方法
template <class RandomAccessIterator,class Distance,class T>
void __make_heap(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{
if(last - first <2) return;
Distance len = last - first;
Distance parent = (len - 1)/2; //找出临时父节点
while(true) //尚未到达顶端，且父节点小于新值，这个循环将父值不断下调
{
__adjust_heap(first,parent,len,T(*(first+parent)));
if(parent == 0) return; parent--;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/105506152
- 点赞
- 收藏
- 关注作者
评论（0）