堆中某個結(jié)點與其父結(jié)點伯顶、左子樹以及右子樹數(shù)組下標(biāo)的關(guān)系
從數(shù)組下標(biāo)為1的位置開始存儲堆：
parent (i) = i / 2
left child (i) = i * 2
right child (i) = i * 2 + 1
從數(shù)組下標(biāo)為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*的數(shù)組
unsigned int n; // 元素個-->size
unsigned int a; // 容量-->capacity
} min_heap_t;
/**
* min_heap_ctor_ - 小頂堆構(gòu)造函數(shù)
* @s：小頂堆
* @return：void
* */
void min_heap_ctor_(min_heap_t* s)
{
s->p = 0;
s->n = 0;
s->a = 0;
}
/**
* min_heap_dtor_ - 小頂堆析構(gòu)函數(shù)
* @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_ - 獲取小頂堆中元素個數(shù)
* @s：小頂堆
* @return：小頂堆中元素個數(shù)
* */
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)
{
// 當(dāng)小頂堆中的容量大小小于要分配空間的大小時峭梳，才進(jìn)行分配空間
if (s->a < n)
{
struct event** p;
unsigned int a = s->a ? s->a * 2 : 8; // 如果容量不為0，則擴(kuò)大2倍捂寿，否則設(shè)為初始值8
if (a < n)
{
a = n;
}
if (!(p = (struct event**)realloc(s->p, a * sizeof(*p)))) // 一般堆使用數(shù)組來保存，使用realloc可以保證空間連續(xù)性
{
return -1;
}
s->p = p;
s->a = a;
}
return 0;
}
/**
* min_heap_shift_up_ - 上浮操作
* @s：小頂堆
* @hole_index：需要上浮操作的元素的數(shù)組下標(biāo)
* @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; // 此小頂堆是從數(shù)組下標(biāo)為0的位置開始存儲元素的蔓彩，可以將獲取父結(jié)點的數(shù)組下標(biāo)封裝為一個函數(shù)
// 尋找e應(yīng)該存放的位置赤嚼，最后再將e存放在尋找到的位置更卒，這比每次swap的效率要高
while (hole_index && min_heap_elem_greater(s->p[parent], e)) // min_heap_elem_greater()返回s->p[parent]>e的結(jié)果
{
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：需要下沉操作的元素的數(shù)組下標(biāo)
* @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); // 獲取當(dāng)前結(jié)點的右子樹
while (min_child <= s->n)
{
// 如果"當(dāng)前結(jié)點無右子樹"或者"右子樹的值大于左子樹的值(小頂堆)"蹂空，就取左子樹
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. 執(zhí)行上浮操作
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：刪除數(shù)組中最后一個元素
// 2. 將數(shù)組中最后一個元素當(dāng)作堆頂返弹，進(jìn)行下沉操作
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結(jié)構(gòu)土陪，而與min_heap_shift_up_()使用的是while結(jié)構(gòu)
// 因為調(diào)用min_heap_shift_up_unconditional_()函數(shù)的條件就是滿足上浮操作的條件
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元素的位置源哩，然后對其進(jìn)行上浮或者下沉操作
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_ - 調(diào)整某個元素的位置励烦。該函數(shù)的作用是坛掠？屉栓？？
* @s：小頂堆
* @e：待調(diào)整的元素
* @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可以保證申請內(nèi)存的連續(xù)性
realloc()原型為extern void *realloc(void *mem_address, unsigned int newsize);骗绕。
先判斷當(dāng)前的指針是否有足夠的連續(xù)空間酬土，如果有撤缴，擴(kuò)大mem_address指向的地址叽唱，并且將mem_address返回，如果空間不夠虎眨，先按照newsize指定的大小分配空間镶摘，將原有數(shù)據(jù)從頭到尾拷貝到新分配的內(nèi)存區(qū)域凄敢，而后釋放原來mem_address所指內(nèi)存區(qū)域(注意：原來指針是自動釋放涝缝，不需要使用free)譬重，同時返回新分配的內(nèi)存區(qū)域的首地址害幅。即重新分配存儲器塊的地址以现。
注意：新的大小可大可小(如果新的大小大于原內(nèi)存大小邑遏，則新分配部分不會被初始化记盒；如果新的大小小于原內(nèi)存大小纪吮，可能會導(dǎo)致數(shù)據(jù)丟失)萎胰。
