目录结构：
.
├── a.out 可执行
├── main.c 测试主程序
└── minheap.h 少许修改的minheap头文件
1、minheap.h
#ifndef _MIN_HEAP_H_
#define _MIN_HEAP_H_
#include <stdlib.h>
struct event
{
union
{
int min_heap_idx; /*堆数组的序号，堆顶为0*/
} ev_timeout_pos;
int ev_timeout; /*key值*/
};
typedef struct min_heap
{
struct event** p;
unsigned n, a;
/*
n表示目前保存了多少个元素
a表示p指向的内存的尺寸（一级指针的个数*指针的大小）
*/
} min_heap_t;
#define mm_malloc(sz) malloc(sz)
#define mm_calloc(n, sz) calloc((n), (sz))
#define mm_strdup(s) strdup(s)
#define mm_realloc(p, sz) realloc((p), (sz))
#define mm_free(p) free(p)
/*key大小的比较函数*/
#define evutil_timercmp(tvp, uvp, cmp) ((tvp cmp uvp)?1:0)
static inline void min_heap_ctor(min_heap_t* s);
static inline void min_heap_dtor(min_heap_t* s);
static inline void min_heap_elem_init(struct event* e);
static inline int min_heap_elt_is_top(const struct event *e);
static inline int min_heap_elem_greater(struct event *a, struct event *b);
static inline int min_heap_empty(min_heap_t* s);
static inline unsigned min_heap_size(min_heap_t* s);
static inline struct event* min_heap_top(min_heap_t* s);
static inline int min_heap_reserve(min_heap_t* s, unsigned n);
static inline int min_heap_push(min_heap_t* s, struct event* e);
static inline struct event* min_heap_pop(min_heap_t* s);
static inline int min_heap_erase(min_heap_t* s, struct event* e);
static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);
/*比较两个event的超时值大小*/
int min_heap_elem_greater(struct event *a, struct event *b)
{
return evutil_timercmp(a->ev_timeout, b->ev_timeout, >);
}
/*初始话定时器小根堆*/
void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
/*销毁定时器小根堆*/
void min_heap_dtor(min_heap_t* s) { if (s->p) mm_free(s->p); }
void min_heap_elem_init(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; }
/*判断是否为空*/
int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
/*返回heap元素值数量*/
unsigned min_heap_size(min_heap_t* s) { return s->n; }
/*返回堆顶元素*/
struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
/*堆元素插入*/
int min_heap_push(min_heap_t* s, struct event* e)
{
if (min_heap_reserve(s, s->n + 1))
return -1;
min_heap_shift_up_(s, s->n++, e);
return 0;
}
/*弹出堆顶元素*/
struct event* min_heap_pop(min_heap_t* s)
{
if (s->n)
{
struct event* e = *s->p;
min_heap_shift_down_(s, 0u, s->p[--s->n]);
e->ev_timeout_pos.min_heap_idx = -1;
return e;
}
return 0;
}
/*判断当前元素是否是堆顶元素*/
int min_heap_elt_is_top(const struct event *e)
{
return e->ev_timeout_pos.min_heap_idx == 0;
}
/*在堆中移除已有的元素，释放操作在外部执行，函数只是解除下标指针的引用*/
int min_heap_erase(min_heap_t* s, struct event* e)
{
if (-1 != e->ev_timeout_pos.min_heap_idx)
{
struct event *last = s->p[--s->n];
unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
/* we replace e with the last element in the heap. We might need to
shift it upward if it is less than its parent, or downward if it is
greater than one or both its children. Since the children are known
to be less than the parent, it can't need to shift both up and
down. */
if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
min_heap_shift_up_(s, e->ev_timeout_pos.min_heap_idx, last);
else
min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);
e->ev_timeout_pos.min_heap_idx = -1;
return 0;
}
return -1;
}
/*
调整内存空间大小，也就是调整p指向的内存区域大小。
凡是涉及到内存大小调整的，都有一个策略问
题，这里采用的是初始大小为8，
每次增大空间时以2倍的速度增加。*/
int min_heap_reserve(min_heap_t* s, unsigned n)
{
if (s->a < n)
{
struct event** p;
unsigned a = s->a ? s->a * 2 : 8;
if (a < n)
a = n;
if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p)))
return -1;
s->p = p;
s->a = a;
}
return 0;
}
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])->ev_timeout_pos.min_heap_idx = hole_index;
hole_index = parent;
parent = (hole_index - 1) / 2;
}
(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
}
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])->ev_timeout_pos.min_heap_idx = hole_index;
hole_index = min_child;
min_child = 2 * (hole_index + 1);
}
(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
}
#endif /* _MIN_HEAP_H_ */
2、main.c
#include "minheap.h"
#include <stdio.h>
min_heap_t stheap;
int main(int argc , char **argv)
{
int i = 0;
struct event *temp = NULL;
int index = 10;
min_heap_ctor(&stheap);
if (min_heap_reserve(&stheap,1 + min_heap_size(&stheap)) == -1)
{
return -1;
}
while(index--)
{
if (min_heap_reserve(&stheap,1 + min_heap_size(&stheap)) == -1)
{
return -1;
}
temp = (struct event *)mm_malloc(sizeof(struct event));
if(!temp)
{
return -1;
}
min_heap_elem_init(temp);
temp->ev_timeout = index;
min_heap_push(&stheap,temp);
}
temp = stheap.p[0];
min_heap_erase(&stheap,temp);
for(i =0;i<stheap.n ;i++)
{
printf("[%d:%d]\n",stheap.p[i]->ev_timeout_pos.min_heap_idx,stheap.p[i]->ev_timeout);
}
#if 0
min_heap_pop(&stheap);
for(i =0;i<stheap.n ;i++)
{
printf("[%d:%d]\n",i,stheap.p[i]->ev_timeout_pos.min_heap_idx,stheap.p[i]->ev_timeout);
}
#endif
return 0;
}
3、push元素
4、覆盖移除下标为3的指针指向
[root@localhost heap]# ./a.out
[0:1]
[1:2]
[2:4]
[3:3]
[4:7]
[5:8]
[6:5]
[7:9]
[8:6]
