网络编程中除了处理IO事件之外,定时事件也同样不可或缺,如定期检测一个客户连接的活动状态、游戏中的技能冷却倒计时以及其他需要使用超时机制的功能。我们的服务器程序中往往需要处理众多的定时事件,因此有效的组织定时事件,使之能在预期时间内被触发且不影响服务器主要逻辑,对我们的服务器性能影响特别大。 我们的web服务器也需要这样一个定时器,定时剔除掉长时间不动的空闲用户,避免他们耗费服务器资源。
一般的做法是将每个定时事件封装成定时器,并使用某种容器类数据结构将所有的定时器保存好,实现对定时事件的统一管理。常用方法有排序链表、红黑树、时间堆(优先级队列)和时间轮。
时间堆的底层实现是由小根堆实现的。小根堆可以保证堆顶元素为最小的。换句话说,是一个时间最小优先的队列,优先级高的元素排在堆顶, 每次插入或删除元素都会将优先级队列中的元素按照优先级高的在前的规则排列。
堆是一个完全二叉树,因此采用顺序存储的方式。本文以小根堆为例进行说明。
<aside> 💡 堆的插入与向上调整算法
</aside>
假设堆使用数组作为底层的实现,那么堆的插入又该如何实现呢?是插入到原堆的头部?还是尾部?亦或是中间? 鉴于原堆已经保持了堆序性,如果插入在头部,相当于所有元素对应的父结点和子结点都会发生变化,这样一来会导致整个堆失效;如果插入在中间的某一位置,则会导致插入位置之后的所有元素对应的父结点和子结点发生变化,这样一来会导致堆的部分失效;如果插入在堆底,则原堆的结构未遭破坏,此时唯一可能不符合堆性质的只是最后一个元素(刚刚插入的元素)的父结点是否比它大/小,即在这个局部是否还满足之前所说的堆序性。
好,现在,可以确定在堆底插入新元素的代价是最小的,那么接下来就是思考在这种情况下如何恢复堆序性。
回顾一下小根堆的性质便不难看出,在此种情形下,对失序的堆执行以下操作即可恢复其堆序性:若新插入结点小于其父结点,则将两者交换。此时并不需要考虑插入结点的兄弟结点(如果有),因为小根堆的性质保证了根结点是小于孩子结点的。
一次交换之后可能没有维护整个小根堆的性质,因此当父结点大于子结点的时候,就一直交换,直到根部,反之就返回。
void HeapTimer::Siftup(size_t i) {
assert(i >= 0 && i < m_heap.size());
size_t j = (i - 1) / 2; //父节点
while (j >= 0) {
if (m_heap[j] < m_heap[i]) {
break;
}
SwapNode(i, j);
i = j;
j = (i - 1) / 2;
}
}
<aside> 💡 堆的向下调整算法
</aside>
假如,堆中的某一个元素的值发生了变化,原来的小根堆被破坏了,此时需要重新维护小根堆。必须得确保根结点的左右子树均为小堆才可。
接下来,就要进行向下调整,确保其最终是个堆。只需三步。