author : Kevin Lynx
什么是min heap ?
首先看什么是heap，heap是這樣一種數(shù)據(jù)結(jié)構(gòu)：1.它首先是一棵完成二叉樹；2.父親節(jié)點(diǎn)始終大于(或其他邏輯關(guān)系
)其孩子節(jié)點(diǎn)。根據(jù)父親節(jié)點(diǎn)與孩子節(jié)點(diǎn)的這種邏輯關(guān)系，我們將heap分類，如果父親節(jié)點(diǎn)小于孩子節(jié)點(diǎn)，那么這個(gè)heap
就是min heap。
就我目前所看到的實(shí)現(xiàn)代碼來看，heap基本上都是用數(shù)組(或者其他的連續(xù)存儲(chǔ)空間)作為其存儲(chǔ)結(jié)構(gòu)的。這可以保證
數(shù)組第一個(gè)元素就是heap的根節(jié)點(diǎn)。這是一個(gè)非常重要的特性，它可以保證我們?cè)谌eap的最小元素時(shí)，其算法復(fù)雜度為
O(1)。
原諒我的教科書式說教，文章后我會(huì)提供我所查閱的比較有用的關(guān)于heap有用的資料。
What Can It Do?
libevent中的min_heap其實(shí)不算做真正的MIN heap。它的節(jié)點(diǎn)值其實(shí)是一個(gè)時(shí)間值。libevent總是保證時(shí)間最晚的節(jié)
點(diǎn)為根節(jié)點(diǎn)。
libevent用這個(gè)數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)IO事件的超時(shí)控制。當(dāng)某個(gè)事件(libevent中的struct event)被添加時(shí)(event_add)，
libevent將此事件按照其超時(shí)時(shí)間(由用戶設(shè)置)保存在min_heap里。然后libevent會(huì)定期地去檢查這個(gè)min_heap，從而實(shí)現(xiàn)
了超時(shí)機(jī)制。
實(shí)現(xiàn)
min_heap相關(guān)源碼主要集中在min_heap.h以及超時(shí)相關(guān)的event.c中。
首先看下min_heap的結(jié)構(gòu)體定義：
typedef struct min_heap
{
struct event** p;
unsigned n, a;
} min_heap_t;
p指向了一個(gè)動(dòng)態(tài)分配的數(shù)組(隨便你怎么說，反正它是一個(gè)由realloc分配的連續(xù)內(nèi)存空間)，數(shù)組元素為event*，這也是
heap中的節(jié)點(diǎn)類型。這里libevent使用連續(xù)空間去保存heap，也就是保存一棵樹。因?yàn)閔eap是完成樹，所以可以保證其元素在
數(shù)組中是連續(xù)的。n表示目前保存了多少個(gè)元素，a表示p指向的內(nèi)存的尺寸。
struct event這個(gè)結(jié)構(gòu)體定義了很多東西，但是我們只關(guān)注兩個(gè)成員：min_heap_idx：表示該event保存在min_heap數(shù)組中
的索引，初始為-1；ev_timeout：該event的超時(shí)時(shí)間，將被用于heap操作中的節(jié)點(diǎn)值比較。
接下來看幾個(gè)與堆操作不大相關(guān)的函數(shù)：
min_heap_elem_greater：比較兩個(gè)event的超時(shí)值大小。
min_heap_size：返回heap元素值數(shù)量。
min_heap_reserve：調(diào)整內(nèi)存空間大小，也就是調(diào)整p指向的內(nèi)存區(qū)域大小。凡是涉及到內(nèi)存大小調(diào)整的，都有一個(gè)策略問
題，這里采用的是初始大小為8，每次增大空間時(shí)以2倍的速度增加。
看幾個(gè)核心的：真正涉及到heap數(shù)據(jù)結(jié)構(gòu)操作的函數(shù)：往堆里插入元素、從堆里取出元素：
相關(guān)函數(shù)為：min_heap_push、min_heap_pop、min_heap_erase、min_heap_shift_up_、min_heap_shift_down_。
heap的核心操作：
- 往堆里插入元素：
往堆里插入元素相對(duì)而言比較簡(jiǎn)單，如圖所示，每一次插入時(shí)都從樹的最右最下(也就是葉子節(jié)點(diǎn))開始。然后比較即將插入
的節(jié)點(diǎn)值與該節(jié)點(diǎn)的父親節(jié)點(diǎn)的值，如果小于父親節(jié)點(diǎn)的話(不用在意這里的比較規(guī)則，上下文一致即可)，那么交換兩個(gè)節(jié)點(diǎn)，
將新的父親節(jié)點(diǎn)與其新的父親節(jié)點(diǎn)繼續(xù)比較。重復(fù)這個(gè)過程，直到比較到根節(jié)點(diǎn)。
libevent實(shí)現(xiàn)這個(gè)過程的函數(shù)主要是min_heap_shift_up_。每一次min_heap_push時(shí)，首先檢查存儲(chǔ)空間是否足夠，然后直接
調(diào)用min_heap_shift_up_插入。主要代碼如下：
void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
{
/**//* 獲取父節(jié)點(diǎn) */
unsigned parent = (hole_index - 1) / 2;
/**//* 只要父節(jié)點(diǎn)還大于子節(jié)點(diǎn)就循環(huán) */
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;
- 從堆里取元素：
大部分時(shí)候，從堆里取元素只局限于取根節(jié)點(diǎn)，因?yàn)檫@個(gè)節(jié)點(diǎn)是最有用的。對(duì)于數(shù)組存儲(chǔ)結(jié)構(gòu)而言，數(shù)組第一個(gè)元素即為根
節(jié)點(diǎn)。取完元素后，我們還需要重新調(diào)整整棵樹以使其依然為一個(gè)heap。
這需要保證兩點(diǎn)：1.依然是完成樹；2.父親節(jié)點(diǎn)依然小于孩子節(jié)點(diǎn)。
在具體實(shí)現(xiàn)heap的取元素操作時(shí)，具體到代碼層次，方法都是有那么點(diǎn)微小差別的。libvent里的操作過程大致如圖所示（實(shí)際上libevent中父節(jié)點(diǎn)的時(shí)間值小于子節(jié)點(diǎn)的時(shí)間值，時(shí)間值的比較通過evutil_timercmp實(shí)現(xiàn)）：
主要過程分為兩步：
1.比較左右孩子節(jié)點(diǎn)，選擇最大的節(jié)點(diǎn)，移到父親節(jié)點(diǎn)上；按照這種方式處理被選擇的孩子節(jié)點(diǎn)，直到?jīng)]有孩子節(jié)點(diǎn)為止。例如，
當(dāng)移除了100這個(gè)節(jié)點(diǎn)后，我們?cè)?00的孩子節(jié)點(diǎn)19和36兩個(gè)節(jié)點(diǎn)里選擇較大節(jié)點(diǎn)，即36，將36放置到100處；然后選擇原來的36的
左右孩子25和1，選25放置于原來的36處；
2.按照以上方式處理后，樹會(huì)出現(xiàn)一個(gè)空缺，例如原先的25節(jié)點(diǎn)，因?yàn)楸灰苿?dòng)到原先的36處，25處就空缺了。因此，為了保證完
成性，就將最右最下的葉子節(jié)點(diǎn)(也就是連續(xù)存儲(chǔ)結(jié)構(gòu)中最后一個(gè)元素)，例如這里的7，移動(dòng)到空缺處，然后按照插入元素的方式處理
新插入的節(jié)點(diǎn)7。
完成整個(gè)過程。
libevent完成這個(gè)過程的函數(shù)主要是min_heap_shift_down_：
/**//* hole_index 為取出的元素的位置，e為最右最下的元素值 */
void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
{
/**//* 取得hole_index的右孩子節(jié)點(diǎn)索引 */
unsigned min_child = 2 * (hole_index + 1);
while(min_child <= s->n)
{
/**//* 有點(diǎn)惡心的一個(gè)表達(dá)式，目的就是取兩個(gè)孩子節(jié)點(diǎn)中較大的那個(gè)孩子索引 */
min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
/**//* 找到了位置，這里似乎是個(gè)優(yōu)化技巧，不知道具體原理 */
if(!(min_heap_elem_greater(e, s->p[min_child])))
break;
/**//* 換位置 */
(s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
/**//* 重復(fù)這個(gè)過程 */
hole_index = min_child;
min_child = 2 * (hole_index + 1);
}
/**//* 執(zhí)行第二步過程，將最右最下的節(jié)點(diǎn)插到空缺處 */
min_heap_shift_up_(s, hole_index, e);
}
STL中的heap
值得一提的是，STL中提供了heap的相關(guān)操作算法，借助于模板的泛化特性，其適用范圍非常廣泛。相關(guān)函數(shù)為：
make_heap, pop_heap, sort_heap, is_heap, sort 。其實(shí)現(xiàn)原理同以上算法差不多，相關(guān)代碼在algorithm里。SGI的
STL在stl_heap.h里。
參考資料：
What is a heap?
Heap_(data_structure)
Heap Remove