author : Kevin Lynx
什么是min heap ?
首先看什么是heap,heap是这样一种数据结构:1.它首先是一棵完成二叉树;2.父亲节点始终大于(或其他逻辑关系
)其孩子节点。根据父亲节点与孩子节点的这种逻辑关系,我们将heap分类,如果父亲节点小于孩子节点,那么这个heap
就是min heap。
就我目前所看到的实现代码来看,heap基本上都是用数组(或者其他的连续存储空间)作为其存储结构的。这可以保证
数组第一个元素就是heap的根节点。这是一个非常重要的特性,它可以保证我们在取heap的最小元素时,其算法复杂度为
O(1)。
原谅我的教科书式说教,文章后我会提供我所查阅的比较有用的关于heap有用的资料。
What Can It Do?
libevent中的min_heap其实不算做真正的MIN heap。它的节点值其实是一个时间值。libevent总是保证时间最晚的节
点为根节点。
libevent用这个数据结构来实现IO事件的超时控制。当某个事件(libevent中的struct event)被添加时(event_add),
libevent将此事件按照其超时时间(由用户设置)保存在min_heap里。然后libevent会定期地去检查这个min_heap,从而实现
了超时机制。
实现
min_heap相关源码主要集中在min_heap.h以及超时相关的event.c中。
首先看下min_heap的结构体定义:
typedef struct min_heap
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
struct event** p;
unsigned n, a;
} min_heap_t;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
p指向了一个动态分配的数组(随便你怎么说,反正它是一个由realloc分配的连续内存空间),数组元素为event*,这也是
heap中的节点类型。这里libevent使用连续空间去保存heap,也就是保存一棵树。因为heap是完成树,所以可以保证其元素在
数组中是连续的。n表示目前保存了多少个元素,a表示p指向的内存的尺寸。
struct event这个结构体定义了很多东西,但是我们只关注两个成员:min_heap_idx:表示该event保存在min_heap数组中
的索引,初始为-1;ev_timeout:该event的超时时间,将被用于heap操作中的节点值比较。
接下来看几个与堆操作不大相关的函数:
min_heap_elem_greater:比较两个event的超时值大小。
min_heap_size:返回heap元素值数量。
min_heap_reserve:调整内存空间大小,也就是调整p指向的内存区域大小。凡是涉及到内存大小调整的,都有一个策略问
题,这里采用的是初始大小为8,每次增大空间时以2倍的速度增加。
看几个核心的:真正涉及到heap数据结构操作的函数:往堆里插入元素、从堆里取出元素:
相关函数为:min_heap_push、min_heap_pop、min_heap_erase、min_heap_shift_up_、min_heap_shift_down_。
heap的核心操作:
- 往堆里插入元素:
往堆里插入元素相对而言比较简单,如图所示,每一次插入时都从树的最右最下(也就是叶子节点)开始。然后比较即将插入
的节点值与该节点的父亲节点的值,如果小于父亲节点的话(不用在意这里的比较规则,上下文一致即可),那么交换两个节点,
将新的父亲节点与其新的父亲节点继续比较。重复这个过程,直到比较到根节点。
libevent实现这个过程的函数主要是min_heap_shift_up_。每一次min_heap_push时,首先检查存储空间是否足够,然后直接
调用min_heap_shift_up_插入。主要代码如下:
void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//* 获取父节点 */
unsigned parent = (hole_index - 1) / 2;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//* 只要父节点还大于子节点就循环 */
while(hole_index && min_heap_elem_greater(s->p[parent], e))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//* 交换位置 */
(s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
hole_index = parent;
parent = (hole_index - 1) / 2;
}
(s->p[hole_index] = e)->min_heap_idx = hole_index;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
- 从堆里取元素:
大部分时候,从堆里取元素只局限于取根节点,因为这个节点是最有用的。对于数组存储结构而言,数组第一个元素即为根
节点。取完元素后,我们还需要重新调整整棵树以使其依然为一个heap。
这需要保证两点:1.依然是完成树;2.父亲节点依然小于孩子节点。
在具体实现heap的取元素操作时,具体到代码层次,方法都是有那么点微小差别的。libvent里的操作过程大致如图所示(实际上libevent中父节点的时间值小于子节点的时间值,时间值的比较通过evutil_timercmp实现):
主要过程分为两步:
1.比较左右孩子节点,选择最大的节点,移到父亲节点上;按照这种方式处理被选择的孩子节点,直到没有孩子节点为止。例如,
当移除了100这个节点后,我们在100的孩子节点19和36两个节点里选择较大节点,即36,将36放置到100处;然后选择原来的36的
左右孩子25和1,选25放置于原来的36处;
2.按照以上方式处理后,树会出现一个空缺,例如原先的25节点,因为被移动到原先的36处,25处就空缺了。因此,为了保证完
成性,就将最右最下的叶子节点(也就是连续存储结构中最后一个元素),例如这里的7,移动到空缺处,然后按照插入元素的方式处理
新插入的节点7。
完成整个过程。
libevent完成这个过程的函数主要是min_heap_shift_down_:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//* hole_index 为取出的元素的位置,e为最右最下的元素值 */
void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//* 取得hole_index的右孩子节点索引 */
unsigned min_child = 2 * (hole_index + 1);
while(min_child <= s->n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//* 有点恶心的一个表达式,目的就是取两个孩子节点中较大的那个孩子索引 */
min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//* 找到了位置,这里似乎是个优化技巧,不知道具体原理 */
if(!(min_heap_elem_greater(e, s->p[min_child])))
break;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//* 换位置 */
(s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//* 重复这个过程 */
hole_index = min_child;
min_child = 2 * (hole_index + 1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//* 执行第二步过程,将最右最下的节点插到空缺处 */
min_heap_shift_up_(s, hole_index, e);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
STL中的heap
值得一提的是,STL中提供了heap的相关操作算法,借助于模板的泛化特性,其适用范围非常广泛。相关函数为:
make_heap, pop_heap, sort_heap, is_heap, sort 。其实现原理同以上算法差不多,相关代码在algorithm里。SGI的
STL在stl_heap.h里。
参考资料:
What is a heap?
Heap_(data_structure)
Heap Remove