上一篇写了写链表，这篇写下堆，这个结构接触的不多，所以正好学习一下libhv中的堆，这个堆的实现比较灵活，即可以是大顶堆也可以是小顶堆，通过比较函数是比大还是比小来区别，当然，如果没有比较函数，就成了无序的，感觉没啥意义，就不讨论无序的堆了。

堆的定义

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

完全二叉树是啥就不解释了。。。。。 下面开始看代码

结构体定义

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 heapheap_compare_fn compare;     
};

初始化

static inline void heap_init(struct heap* heap, heap_compare_fn fn) {heap->root = NULL;  heap->nelts = 0;heap->compare = fn;  //设置比较函数，确定到底是大顶堆还是小顶堆
}

初始化后，该堆就是一个没有根的节点个数为0的空堆。

插入操作

static inline void heap_insert(struct heap* heap, struct heap_node* node) {// get last => insert node => sift up// 0: left, 1: rightint path = 0;int n,d;++heap->nelts;  //结点个数加1// 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 pathstruct heap_node* parent = heap->root;while(d > 1) {parent = (path & 1) ? parent->right : parent->left;--d;path >>= 1;}// insert nodenode->parent = parent;    //设置node的父节点if (parent == NULL) heap->root = node;  //如果父节点为NULL，说明新加入的节点是根结点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);}}
}

最开始获取path是比较有趣的，这里的path功能就是下一个结点的路径，表示方法是1代表右结点，0代表左节点。举个例子：

假设我想新加一个结点G，那么下一个位置就是C的右孩子，在这个堆中G的路径就是  A  --> A的右孩子C --> C的右孩子G；而path就等于 11B（二进制），其中低位的1表示A-->C，高位的1代表C-->G。那么在看这个for循环：

    for (d = 0, n = heap->nelts; n >= 2; ++d, n>>=1) {path = (path << 1) | (n & 1);}

d代表层级，n表示判断第几个节点，第一次for循环判断最后一个节点G，然后向上查询，也就是说，第一个先查G是其父节点C的左孩子还是右孩子，方法是使用(n & 1)，如果为1，表示右孩子，如果为0表示左孩子。其实就是看n是奇数还是偶数，是奇数就是右孩子，是偶数就是左孩子。因为第一次判断n==7是奇数，所以path=1B；第二次for循环判断C是其父节点的左孩子还是右孩子，因为C是第三个节点，是奇数，所以也是右孩子，path=11B；这样就可以做到如何从根节点找到G。

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

知道了path的意思，上面这部分代码就很简单了，查找G的父节点，从heap->root根结点A开始遍历，查找d-1层，也就是查找到C为止。

最后比较麻烦的就是在将G加入堆后，要按照大顶堆或者小顶堆排序，假设该堆是小顶堆，如果G的值小于C，那么需要交换C和G的位置，交互完后，G的父结点就是A，需要再比较G和A的大小，如果G小于A，要继续交换G和A的位置，最后的结果为：

当然了，如果G比C大，就不需要交换位置。

最后看一下交换位置的函数

//交换parent和child的位置
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的父结点为NULL，说明parent是根节点，所以child就成了新的根if (pparent == NULL) heap->root = child;//判断parent是其父节点的左孩子还是右孩子，child替代parent成了parent父节点的孩子else if (pparent->left == parent) pparent->left = child; else if (pparent->right == parent) pparent->right = child;//parent以后成了child的孩子节点的父结点if (lchild) lchild->parent = parent;if (rchild) rchild->parent = parent;child->parent  = pparent;if (parent->left == child) {sibling = parent->right;child->left = parent;child->right = sibling;} else {sibling = parent->left;child->left = sibling;child->right = parent;}if (sibling) sibling->parent = child;parent->parent = child;parent->left   = lchild;parent->right  = rchild;
}

看似一堆的指针操作，很麻烦，实际上非常简单。以第一张图为例，假设我要交换C和G的位置，那么需要改变这么几点：修改A的孩子为G；修改C的父结点为G，并且C成为了G的孩子结点的新父结点；修改G的父节点为A，修改G的孩子节点为C和过去的兄弟节点，假如存在的话。

删除操作

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: rightint 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;//父结点为NULL，也就是根节点为NULL，说明为空堆if (parent == NULL) {return;}//右结点和左结点，因为后面要把最后一个节点和node交换，而将父节点//的孩子赋值为NULL，相当于直接把交换后的node删除了else if (path & 1) {last = parent->right;parent->right = NULL;}else {last = parent->left;parent->left = NULL;}//last为NULL，说明只有一个根结点if (last == NULL) {if (heap->root == node) {heap->root = NULL;}return;}//把last替换到node原来的位置，node被删除heap_replace(heap, node, last);node->parent = node->left = node->right = NULL;//因为last替换到node原来的位置后，堆的顺序可能被打乱，//所以要重新排序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);}
}

删除操作的方法为先把要删除的结点与最后一个结点互换，然后删除该结点，再调整新堆的顺序。举个例子，假设我要把第一张图的B结点删除，交换完后是这样的：

因为B成了最后一个结点，直接把C的右孩子赋值为NULL，就相当于删除了B，对其他的结点不会产生影响。但是G的位置需要调整，因为G的值可能比D或者E大，那么就需要由D和E中较小的与G交换。当然了，在这个图中，A不可能比G大，所以不用交换A和G的位置。但是这是有可能发生的，如果删除的不是B而是D，G和D交换了之后，G有可能小于B，那么就需要交换G和B的位置。

heap_remove函数调用了一个新的函数heap_replace，实现了替换功能，实际上该函数比heap_swap更简单，因为替换就是交换的一半功能而已，源码不再注释了：

// 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->parentif (s->parent == NULL) heap->root = r;else if (s->parent->left == s) s->parent->left = r;else if (s->parent->right == s) s->parent->right = r;if (s->left) s->left->parent = r;if (s->right) s->right->parent = r;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);
}

以上大体就是libhv中heap.h的全部功能，理解起来也并不复杂。