数据结构-02-Heap

Data Structure , , Comments

在阅读 libevent 库中另外一个用来存储事件的第二个结构就是小根堆，这里重新学习一下它的实现

代码路径:minheap-internal.h

1
2
3
4
5
typedef struct min_heap
{
	struct event** p;
	size_t n, a;	// n 表示堆的元素数目，a 表示当前分配的内存空间大小
} min_heap_t;

struct event** p 区别与使用数组进行存储，这样就可以实现动态扩容

堆初始化

一开始没有元素，而要做的就是初始化一个最小堆对象 min_heap_t

1
2
3
4
//event.c:650 event_base_new_with_config
min_heap_ctor_(&base->timeheap);

void min_heap_ctor_(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }

初始化堆，这里有一个小技巧就是将 s->p= 0 , 就是不指向任何对象，相当于 NULL，min_heap_t* a = 0;，同时堆的分配内容大小 a 一开始并没指定**(懒加载形式)**

其他辅助函数包括

1
2
3
4
5
6
int min_heap_empty_(min_heap_t* s) { return 0 == s->n; }	//堆是否为空
size_t 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; }	//堆顶节点
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 = EV_SIZE_MAX; }

添加节点

1
2
3
4
//event.c:2217 event_assign

min_heap_elem_init_(ev);
void min_heap_elem_init_(struct event* e) { e->ev_timeout_pos.min_heap_idx = EV_SIZE_MAX; }

在添加节点的时候，首先指定节点在堆中的索引是 EV_SIZE_MAX，表示并没有加入到堆中，接着加入到堆中

1
2
3
4
5
6
7
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;
}

这里就发生了两步操作

  1. 因为可能堆已经满了，所以需要将堆进行扩容 min_heap_reserve_
  2. 堆化，需要调整成小顶堆

扩容

首次分配的容量大小是8，后续依次加倍

问题1：如果节点新增很多，会不会导致内存分配暴涨？

golang 的 map 有一个 2倍增长到了一定数量再1.25倍增长的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int min_heap_reserve_(min_heap_t* s, size_t n)
{
	if (s->a < n)	//判断容量是否不够
	{
		struct event** p;
		size_t a = s->a ? s->a * 2 : 8;	// 小于8则使用8，否则加倍增长
		if (a < n)	//如果仍然小于n, 则直接使用 n 
			a = n;
		if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p)))
			return -1;
		s->p = p;
		s->a = a;
	}
	return 0;
}
  1. 当容量不够的时候，需要进行扩容操作，不需要考虑 golang map 那种因为装载量过大而影响查询效率的情况
  2. 容量首先是8，然后依次递增，当等待事件比较多，注意内存占用(一大块内存)
  3. 使用 realloc 操作，直接保留了原来的内容(realloc 的底层并不一定在原有的基础上，因为无法保证内存后面是否仍然有足够的空闲空间）

向上调整

元素入堆的基本流程是：

  1. 将元素添加到堆尾(堆最后一个元素)

  2. 将元素与父节点进行比较

    a. 如果比父节点大则与父节点交换位置 然后重复 1～2 操作

    b. 如果不比父节点大则停止入堆，完成元素添加

接着看它的实际操作

1
2
3
4
5
6
7
8
9
10
11
12
13
//min_heap_shift_up_(s, s->n++, e);
void min_heap_shift_up_(min_heap_t* s, size_t hole_index, struct event* e)
{
    //找到节点的父节点
    size_t 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;
}
  1. hole_index 一开始为堆的最后一个元素的索引，即当前事件 e 的位置
  2. 找到最后一个节点的父节点 (hole_index - 1) / 2;
  3. 如果当前位置 hole_index 还不是堆顶(hole_index != 0 )且 父节点超时时间比自己大
    • 当前元素等于父节点，索引位置更新为 hole_index
    • 当前索引 hole_index 为父节点索引，hole_index = parent;
    • 找到父节点位置
    • 重复操作 3
  4. 更新当前节点为e，设置索引为 hole_index

比较逻辑则是使用超时时间进行对比

1
2
3
4
5
6
7
8
#define min_heap_elem_greater(a, b) \
	(evutil_timercmp(&(a)->ev_timeout, &(b)->ev_timeout, >))

//如果秒相同就是用毫秒
#define	evutil_timercmp(tvp, uvp, cmp)					\
	(((tvp)->tv_sec == (uvp)->tv_sec) ?				\
	 ((tvp)->tv_usec cmp (uvp)->tv_usec) :				\
	 ((tvp)->tv_sec cmp (uvp)->tv_sec))

弹出节点

有增加就有删除，出堆常规操作是

  1. 将堆顶与堆尾元素进行交换
  2. 将堆尾元素出堆
  3. 从对顶元素开始从上到下，与子节点比较交换

看看它是如何做到的

1
2
3
4
5
6
7
8
9
10
11
struct event* min_heap_pop_(min_heap_t* s)
{
	if (s->n)
	{
		struct event* e = *s->p;
		min_heap_shift_down_(s, 0, s->p[--s->n]);
		e->ev_timeout_pos.min_heap_idx = EV_SIZE_MAX;
		return e;
	}
	return 0;
}
  1. --s->n 因为要弹出，所以 数量减 1，s->p[--s->n] 指向堆尾
  2. 如果堆元素数量大于 0，记录堆顶事件。否则返回 0(与前面一样，0 指向指针表示 NULL)
  3. 向下调整，注意最后一个节点指向的是最后一个节点
  4. 更新出堆事件的索引(表示不在堆里面)

向下调整

将 hole_index 与 struct event* e 进行交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void min_heap_shift_down_(min_heap_t* s, size_t hole_index, struct event* e)
{
		size_t 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;
}

  1. 找到节点的右子节点 min_child

  2. 如果右节点存在(不应该超过数目上线)

    • 找到左右节点种较大的

    • 如果当前超时时间比子节点小则停止

      为什么有 min_child == s->n 的比较操作，感觉没有必要！！因为 while (min_child <= s->n) 已经判断了

    • 当前节点为子节点，并更新索引

    • 更新当前节点位置

    • 找到当前节点的右子节点

  3. 当前位置设置为 e，并更新事件的索引

删除元素

删除元素常用于事件发生异常，需要从堆中直接删除而不是从堆顶，这个时候就会出现堆空洞的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int min_heap_erase_(min_heap_t* s, struct event* e)
{
	if (EV_SIZE_MAX != e->ev_timeout_pos.min_heap_idx)
	{
		struct event *last = s->p[--s->n];
		size_t parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
		if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
			min_heap_shift_up_unconditional_(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 = EV_SIZE_MAX;
		return 0;
	}
	return -1;
}
  • 如果 e->ev_timeout_pos.min_heap_idx != EV_SIZE_MAX 表示已经不在堆中了，添加和弹出的时候都会更新这个索引
  • 获取堆尾元素
  • 获取事件的父节点
  • 如果事件不在堆顶而且父结点大于最后一个节点
    • 向上调整
  • 如果事件在堆顶，类似 min_heap_pop_
    • 向下调整

向上调整2

这里为了防止空洞，出现了一个不一样的操作 min_heap_shift_up_unconditional_

1
2
3
4
5
6
7
8
9
10
11
void min_heap_shift_up_unconditional_(min_heap_t* s, size_t hole_index, struct event* e)
{
    size_t parent = (hole_index - 1) / 2;
    do
    {
	(s->p[hole_index] = s->p[parent])->ev_timeout_pos.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)->ev_timeout_pos.min_heap_idx = hole_index;
}
  1. 首先找到当前元素的父节点
  2. 将父节点更新到当前位置，并跟新索引
  3. 设置当前位置为父节点，找到父节点的父节点 parent2
  4. 如果 parent2 不是堆顶，而且 parent2 大于 last，那么重复 2~3操作（感觉不会，因为是小根堆）
  5. 更新 last 到合适的位置

也就是说通过 将 last 填补到要删除元素的位置，解决空洞问题。

问题1：min_heap_shift_up_unconditional_ 与 min_heap_shift_up_ 不同的是，后者先判断了 当前位置以及 当前位置事件与 e 的大小，为什么要做这个区别？

答：是因为前者的位置肯定不是堆顶(走乡下条)

问题2：min_heap_erase_ 删除元素中为什么会出现向下调整与向上调整

答：首先需要明白向上调整与向下调整的作用分别是什么，

向下调整：被用于在删除堆顶元素后，将最后一个元素移到堆顶并逐步将其“下沉”至合适的位置，以保持堆的有序性质。

向上调整：被用于在向堆中插入新元素后，将其逐步“上浮”至合适的位置，以保持堆的有序性质

如果删除位置不是堆顶元素，且父节点大于 last 。那么根据小根堆的性质，last 应该从这个位置开始向上调整

如果删除位置是堆顶元素或者父节点小于last。那么根据小根堆的性质，last应该在删除位置的下发（或不变）

参考链接

  1. https://www.hello-algo.com/chapter_heap/heap/
  2. https://www.hello-algo.com/chapter_sorting/heap_sort/