上一篇分析了libhv里面用到的鏈表的實作，今天我們看一下定時器超時事件中用到的堆得實作，

堆定義

1.堆中的某個節點總是不大于或不小于其父親節點
2.堆總是一顆完全二叉樹

那么，最大堆就是父節點比每一個子節點值都要大，最小堆就是父節點比每一個子節點值要小，
例子（最小堆)

完全二叉樹的定義

對于一個樹高為h的二叉樹，如果其第0層至第h-1層的節點都滿，如果最下面一層節點不滿，則所有的節點在左邊的連續排列，空位都在右邊，這樣的二叉樹就是一棵完全二叉樹

原始碼分析

結構體的定義

struct heap_node {
    struct heap_node* parent; //父節點
    struct heap_node* left;	  //左孩子
    struct heap_node* right;  //右孩子
};

typedef int (*heap_compare_fn)(const struct heap_node* lhs, const struct heap_node* rhs);
struct heap {
    struct heap_node* root;  // 根節點
    int nelts;				 // 節點的個數
    // if compare is less_than, root is min of heap
    // if compare is larger_than, root is max of heap
    heap_compare_fn compare;
};

堆初始化

static inline void heap_init(struct heap* heap, heap_compare_fn fn) {
    heap->root = NULL;  
    heap->nelts = 0;
    heap->compare = fn;  //確定最大堆還是最小堆
}

節點插入
在堆中，節點的插入主要分為兩個步驟：
1.將節點插入到堆得尾部，
2.調整節點的位置，使其滿足堆得特性，
例如：

插入節點2

調整位置


這就是節點插入的程序，下面看一下libhv怎么處理的

static inline void heap_insert(struct heap* heap, struct heap_node* node) {
    // get last => insert node => sift up
    // 0: left, 1: right
    int path = 0;
    int n,d;
    ++heap->nelts;
    // traverse from bottom to up, get path of last node
    for (d = 0, n = heap->nelts; n >= 2; ++d, n>>=1) {
        path = (path << 1) | (n & 1);
    }

    // get last->parent by path
    struct heap_node* parent = heap->root;
    while(d > 1) {
        parent = (path & 1) ? parent->right : parent->left;
        --d;
        path >>= 1;
    }

    // insert node
    node->parent = parent;
    if (parent == NULL) heap->root = node;
    else if (path & 1) parent->right = node;
    else parent->left = node;

    // sift up
    if (heap->compare) {
        while (node->parent && heap->compare(node, node->parent)) {
            heap_swap(heap, node->parent, node);
        }
    }
}

程序就是

// get last => insert node => sift up

先看怎么get last,也就是獲取節點插入的位置

   // traverse from bottom to up, get path of last node
    for (d = 0, n = heap->nelts; n >= 2; ++d, n>>=1) {
        path = (path << 1) | (n & 1);
    }

這里是獲取插入節點的路徑，從根出發，沿怎樣的路徑找到插入的位置，
輔以圖講解

現在我們要插入節點7，
那么 n= heap->nelts = 7. 各變數的變化程序是：

n:7 ? 3 ? 1
d:0 ? 1 ? 2
path:0001 ?0011

此時得到的路徑為11B，0為左孩子，1為右孩子，也就是說，從根出發，根的右孩子，右孩子的右孩子

看一下代碼

  // get last->parent by path
    struct heap_node* parent = heap->root;
    while(d > 1) {
        parent = (path & 1) ? parent->right : parent->left;
        --d;
        path >>= 1;
    }

那么parent指向的就是3節點
插入節點

 // insert node
    node->parent = parent;    //設定父節點
    if (parent == NULL) heap->root = node;  //如果父節點為NULL，說明新加入的節點是根結點
    else if (path & 1) parent->right = node; //新加入的節點是其父節點的右結點
    else parent->left = node;   //新加入的節點是其父節點的左節點

接下來就是調整位置，使其滿足堆得定義

if (heap->compare) {
        while (node->parent && heap->compare(node, node->parent)) {
            heap_swap(heap, node->parent, node); //交換節點與父節點
        }
    }

static inline void heap_swap(struct heap* heap, struct heap_node* parent, struct heap_node* child) {
    assert(child->parent == parent && (parent->left == child || parent->right == child));
    //parent的父節點
    struct heap_node* pparent = parent->parent;
    //child的左孩子
    struct heap_node* lchild = child->left;
    //child的右孩子
    struct heap_node* rchild = child->right;
    struct heap_node* sibling = NULL;
	
	//[parent的父節點更換孩子為child]
	//如果parent的父節點為空，說明parent是根節點
    if (pparent == NULL) heap->root = child;
    //如果parent是父節點的左孩子，則把左孩子指向child
    else if (pparent->left == parent) pparent->left = child;
    //如果parent是父節點的右孩子，則把右孩子指向child
    else if (pparent->right == parent) pparent->right = child;
    
    //[child的孩子更換父節點]
    //如果child有左孩子，則把左孩子指向parent
    if (lchild) lchild->parent = parent;
     //如果child有左孩子，則把左孩子指向parent
    if (rchild) rchild->parent = parent;

	//child更換parent
    child->parent  = pparent;
   //如果child是parent的左孩子，則把parent的變為child的左孩子
    if (parent->left == child) {
        sibling = parent->right;
        child->left = parent;
        child->right = sibling;
    }
    //如果child是parent的右孩子，則把parent的變為child的右孩子
    else {
        sibling = parent->left;
        child->left = sibling;
        child->right = parent;
    }
    //將parent另一個孩子的父節點改為child
    if (sibling) sibling->parent = child;

    parent->parent = child;
    parent->left   = lchild;
    parent->right  = rchild;
}

節點洗掉

static inline void heap_remove(struct heap* heap, struct heap_node* node) {
    if (heap->nelts == 0)   return;
    // get last => replace node with last => sift down and sift up
    // 0: left, 1: right
    int path = 0;
    int n,d;
    // traverse from bottom to up, get path of last node
    //獲取最后一個節點的路徑
    for (d = 0, n = heap->nelts; n >= 2; ++d, n>>=1) {
        path = (path << 1) | (n & 1);
    }
    --heap->nelts;

    // get last->parent by path
    //獲取最后一個節點的父節點
    struct heap_node* parent = heap->root;
    while(d > 1) {
        parent = (path & 1) ? parent->right : parent->left;
        --d;
        path >>= 1;
    }

    // replace node with last
    struct heap_node* last = NULL;
    if (parent == NULL) {
        return;
    }
    //獲取最后一個節點，并在堆中將該位置賦值為NULL，相當于把node洗掉了
    else if (path & 1) {
        last = parent->right;
        parent->right = NULL;
    }
    else {
        last = parent->left;
        parent->left = NULL;
    }
    //說明只有一個根節點
    if (last == NULL) {
        if (heap->root == node) {
            heap->root = NULL;
        }
        return;
    }
    //交換node和last
    heap_replace(heap, node, last);
    node->parent = node->left = node->right = NULL;

    if (!heap->compare) return;
    struct heap_node* v = last;
    struct heap_node* est = NULL;
    // sift down
    //last有可能比過去node的孩子結點大，那么需要將last向下移動
    while (1) {
        est = v;
        if (v->left) est = heap->compare(est, v->left) ? est : v->left;
        if (v->right) est = heap->compare(est, v->right) ? est : v->right;
        if (est == v) break;
        heap_swap(heap, v, est);
    }
    // sift up
    //last有可能比過去node的父結點小，那么需要將last向上移動
    while (v->parent && heap->compare(v, v->parent)) {
        heap_swap(heap, v->parent, v);
    }
}

洗掉的大體程序就是，把洗掉的節點和最后一個節點交換，然后再調整交換后的節點的位置，使其滿足堆得定義，

// replace s with r
static inline void heap_replace(struct heap* heap, struct heap_node* s, struct heap_node* r) {
    // s->parent->child, s->left->parent, s->right->parent
    //s為根節點
    if (s->parent == NULL) heap->root = r;
    //如果s是父節點的左孩子，則r變為s左孩子
    else if (s->parent->left == s) s->parent->left = r;
    //如果s是父節點的右孩子，則r變為s右孩子
    else if (s->parent->right == s) s->parent->right = r;

    //把s的孩子的父節點變為r
    if (s->left) s->left->parent = r;
    if (s->right) s->right->parent = r;
    r的父節點，孩子節點變為s的父節點和孩子節點
    if (r) {
        //*r = *s;
        r->parent = s->parent;
        r->left = s->left;
        r->right = s->right;
    }
}

洗掉根節點

static inline void heap_dequeue(struct heap* heap) {
    heap_remove(heap, heap->root);
}

再看一下堆在定時器結構體里的應用

#define HTIMER_FIELDS                   \
    HEVENT_FIELDS                       \
    uint32_t    repeat;                 \
    uint64_t    next_timeout;           \
    struct heap_node node;

struct htimer_s {
    HTIMER_FIELDS
};

#define TIMER_ENTRY(p)          container_of(p, htimer_t, node)

和鏈表使用的思想是一樣的，

以上就是libhv里堆的實作，