是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)其左子节点和右子节点的值。

最常见的时间堆一般用最小堆实现。

最小堆:根节点的键值是所有堆节点键值中最小者的堆

如下图:

对于定时器来说,如果堆顶元素比当前的时间还要大,说明堆项内所有元素都比当前时间大,进而说明这个时刻我们还没有必要对时间堆进行任何处理。定时检查的时间复杂度是 ?(1) 。

当我们发现堆项的元素小于当前时间时,说明可能已经有一批事件过期了,这时进行正常的弹出的堆调操作就好。每次堆调整的时间复杂度是 ?(????) 。

Go 自身的内置定时器就是用时间堆实现的,不过使用的不是二叉树堆,而是扁平一些的四叉堆:

性质:父节点比其4个子节点都小,子节点之间没有特别的大小关系要求。

四叉堆中元素超时和堆调整与二叉堆没有本质区别。

最后编辑: kuteng  文档更新时间: 2022-03-22 19:29   作者:kuteng