libevent中的小顶堆
2019-04-27 本文已影响0人
jiangling500
堆中某个结点与其父结点、左子树以及右子树数组下标的关系
从数组下标为1的位置开始存储堆：
parent (i) = i / 2
left child (i) = i * 2
right child (i) = i * 2 + 1
从数组下标为0的位置开始存储堆：
parent (i) = (i - 1) / 2
left child (i) = 2 * i + 1;
right child (i) = 2 * i + 2;
libevent中封装的小顶堆
struct event
{
int min_heap_idx; // 在小顶堆中的索引，初始化为-1，可用于判断元素是否位于小顶堆中
// TODO：添加其他字段
};
// 小顶堆
typedef struct min_heap
{
struct event** p; // struct event* p[]，即p指向元素类型为struct event*的数组
unsigned int n; // 元素个-->size
unsigned int a; // 容量-->capacity
} min_heap_t;
/**
* min_heap_ctor_ - 小顶堆构造函数
* @s：小顶堆
* @return：void
* */
void min_heap_ctor_(min_heap_t* s)
{
s->p = 0;
s->n = 0;
s->a = 0;
}
/**
* min_heap_dtor_ - 小顶堆析构函数
* @s：小顶堆
* @return：void
* */
void min_heap_dtor_(min_heap_t* s)
{
if (s->p)
{
free(s->p);
}
}
/**
* min_heap_empty_ - 判断小顶堆是否为空
* @s：小顶堆
* @return：空返回true，非空返回false
* */
int min_heap_empty_(min_heap_t* s)
{
return 0u == s->n;
}
/**
* min_heap_size_ - 获取小顶堆中元素个数
* @s：小顶堆
* @return：小顶堆中元素个数
* */
unsigned min_heap_size_(min_heap_t* s)
{
return s->n;
}
/**
* min_heap_elem_init_ - 初始化元素在小顶堆中的索引值-1
* @e：元素
* @return：void
* */
void min_heap_elem_init_(struct event* e)
{
e->min_heap_idx = -1;
}
/**
* min_heap_top_ - 获取堆顶元素
* @s：小顶堆
* @return：如果小顶堆为空，则返回NULL，否则返回堆顶元素
* */
struct event* min_heap_top_(min_heap_t* s)
{
return s->n ? *s->p : 0; // 注意：*s->p为*(s->p)
}
/**
* min_heap_reserve_ - 分配空间
* @s：小顶堆
* @n：分配空间大小
* @return：成功返回0，失败返回-1
* */
int min_heap_reserve_(min_heap_t* s, unsigned int n)
{
// 当小顶堆中的容量大小小于要分配空间的大小时，才进行分配空间
if (s->a < n)
{
struct event** p;
unsigned int a = s->a ? s->a * 2 : 8; // 如果容量不为0，则扩大2倍，否则设为初始值8
if (a < n)
{
a = n;
}
if (!(p = (struct event**)realloc(s->p, a * sizeof(*p)))) // 一般堆使用数组来保存，使用realloc可以保证空间连续性
{
return -1;
}
s->p = p;
s->a = a;
}
return 0;
}
/**
* min_heap_shift_up_ - 上浮操作
* @s：小顶堆
* @hole_index：需要上浮操作的元素的数组下标
* @e：需要上浮操作的元素
* @return：void
* */
void min_heap_shift_up_(min_heap_t* s, unsigned int hole_index, struct event* e)
{
unsigned int parent = (hole_index - 1) / 2; // 此小顶堆是从数组下标为0的位置开始存储元素的，可以将获取父结点的数组下标封装为一个函数
// 寻找e应该存放的位置，最后再将e存放在寻找到的位置，这比每次swap的效率要高
while (hole_index && min_heap_elem_greater(s->p[parent], e)) // min_heap_elem_greater()返回s->p[parent]>e的结果
{
s->p[hole_index] = s->p[parent];
s->p[hole_index]->min_heap_idx = hole_index;
hole_index = parent;
parent = (hole_index - 1) / 2;
}
s->p[hole_index] = e;
s->p[hole_index]->min_heap_idx = hole_index;
}
/**
* min_heap_shift_down_ - 下沉操作
* @s：小顶堆
* @hole_index：需要下沉操作的元素的数组下标
* @e：需要下沉操作的元素
* @return：void
* */
void min_heap_shift_down_(min_heap_t* s, unsigned int hole_index, struct event* e)
{
unsigned int 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];
s->p[hole_index]->min_heap_idx = hole_index;
hole_index = min_child;
min_child = 2 * (hole_index + 1);
}
s->p[hole_index] = e;
s->p[hole_index]->min_heap_idx = hole_index;
}
/**
* min_heap_push_ - 向小顶堆中添加一个元素
* @s：小顶堆
* @e：添加的元素
* @return：成功返回0，失败返回-1
* */
int min_heap_push_(min_heap_t* s, struct event* e)
{
// 1. 分配所需空间
if (min_heap_reserve_(s, s->n + 1))
{
return -1;
}
// 2. 执行上浮操作
min_heap_shift_up_(s, s->n++, e);
return 0;
}
/**
* min_heap_pop_ - 取走堆顶元素
* @s：小顶堆
* @return：成功返回堆顶元素，失败返回NULL(堆中无元素)
* */
struct event* min_heap_pop_(min_heap_t* s)
{
if (s->n)
{
struct event* e = *(s->p);
// 1. --s->n：删除数组中最后一个元素
// 2. 将数组中最后一个元素当作堆顶，进行下沉操作
min_heap_shift_down_(s, 0u, s->p[--s->n]); // 如果只是访问最后一个元素的话，使用s->p[s->n - 1]
e->min_heap_idx = -1;
return e;
}
return 0;
}
/**
* min_heap_elt_is_top_ - 判断某个元素是否是堆顶元素
* @e：待判断的元素
* @return：是的话返回1，否的话返回0
* */
int min_heap_elt_is_top_(const struct event *e)
{
return e->min_heap_idx == 0;
}
/**
* min_heap_shift_up_unconditional_ - 上浮操作，与min_heap_shift_up_()基本相同
* @s：小顶堆
* @hole_index：
* @e：
* @return：void
* */
void min_heap_shift_up_unconditional_(min_heap_t* s, unsigned int hole_index, struct event* e)
{
unsigned parent = (hole_index - 1) / 2;
// 这里使用的是do-while结构，而与min_heap_shift_up_()使用的是while结构
// 因为调用min_heap_shift_up_unconditional_()函数的条件就是满足上浮操作的条件
do
{
s->p[hole_index] = s->p[parent];
s->p[hole_index]->min_heap_idx = hole_index;
hole_index = parent;
parent = (hole_index - 1) / 2;
} while (hole_index && min_heap_elem_greater(s->p[parent], e));
s->p[hole_index] = e;
s->p[hole_index]->min_heap_idx = hole_index;
}
/**
* min_heap_erase_ - 删除小顶端中的某个元素
* @s：小顶堆
* @e：待删除的元素
* @return：成功返回0，失败返回-1
* */
int min_heap_erase_(min_heap_t* s, struct event* e)
{
// 首先判断要删除的元素是否位于小顶堆中
if (-1 != e->min_heap_idx)
{
// 删除小顶堆中的最后一个元素
struct event *last = s->p[--s->n];
unsigned parent = (e->min_heap_idx - 1) / 2;
// 将小顶堆中的最后一个元素替换到待删除e元素的位置，然后对其进行上浮或者下沉操作
if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
{
min_heap_shift_up_unconditional_(s, e->min_heap_idx, last);
}
else
{
min_heap_shift_down_(s, e->min_heap_idx, last);
}
e->min_heap_idx = -1;
return 0;
}
return -1;
}
/**
* min_heap_adjust_ - 调整某个元素的位置。该函数的作用是？？？
* @s：小顶堆
* @e：待调整的元素
* @return：成功返回0，失败返回-1
* */
int min_heap_adjust_(min_heap_t *s, struct event *e)
{
// 如果该元素不在小顶堆中，则添加到小顶堆中
if (-1 == e->min_heap_idx)
{
return min_heap_push_(s, e);
}
else
{
unsigned parent = (e->min_heap_idx - 1) / 2;
/* The position of e has changed; we shift it up or down
* as needed. We can't need to do both. */
if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], e)
{
min_heap_shift_up_unconditional_(s, e->min_heap_idx, e);
}
else
{
min_heap_shift_down_(s, e->min_heap_idx, e);
}
return 0;
}
}
realloc可以保证申请内存的连续性
realloc()原型为extern void *realloc(void *mem_address, unsigned int newsize);。
先判断当前的指针是否有足够的连续空间，如果有，扩大mem_address指向的地址，并且将mem_address返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域(注意：原来指针是自动释放，不需要使用free)，同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。
注意：新的大小可大可小(如果新的大小大于原内存大小，则新分配部分不会被初始化；如果新的大小小于原内存大小，可能会导致数据丢失)。
