什么是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 
{ 
    struct event** p; 
    unsigned n, a; 
} min_heap_t; 

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) 
{ 
    /* 获取父节点 */ 
    unsigned parent = (hole_index - 1) / 2; 
    /* 只要父节点还大于子节点就循环 */ 
    while(hole_index && min_heap_elem_greater(s->p[parent], e)) 
    { 
        /* 交换位置 */ 
        (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; 

- 从堆里取元素：
    大部分时候，从堆里取元素只局限于取根节点，因为这个节点是最有用的。对于数组存储结构而言，数组第一个元素即为根节点。取完元素后，我们还需要重新调整整棵树以使其依然为一个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_：

/* hole_index 为取出的元素的位置，e为最右最下的元素值 */ 
void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e) 
{ 
    /* 取得hole_index的右孩子节点索引 */ 
    unsigned min_child = 2 * (hole_index + 1); 
    while(min_child <= s->n) 
    { 
/* 有点恶心的一个表达式，目的就是取两个孩子节点中较大的那个孩子索引 */ 
min_child -= min_child == s->n
 || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]); 
/* 找到了位置，这里似乎是个优化技巧，不知道具体原理 */ 
if(!(min_heap_elem_greater(e, s->p[min_child]))) 
break; 
/* 换位置 */ 
(s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index; 
/* 重复这个过程 */ 
hole_index = min_child; 
min_child = 2 * (hole_index + 1); 
    } 
    /* 执行第二步过程，将最右最下的节点插到空缺处 */ 
    min_heap_shift_up_(s, hole_index,  e); 
}  

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