为什么Golang的Timer实现使用四叉堆而不是二叉堆

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

1.引言

Golang在Timer(计时器)的实现中使用了四叉堆，而不是常见的二叉堆，这个问题引起了我的兴趣。

对于这个问题，网上的解释是这样的

但是我仔细查阅了资料以后，有了点有趣的发现。

2.说明

假设: 堆为d叉堆，堆中共有n个节点
备注: 时间复杂度的证明见d-ary heap

Timer最常见的2个操作

1）Insert()

添加一个计时器。涉及 sift-up（上推）操作，时间复杂度为O(log n / log d)

Python代码

import math
result = math.log(n, d)

时间消耗（需要交换或者比较的次数）

n(数量)	二叉堆	四叉堆	八叉堆
1w	13.3	6.64	4.43
10w	16.61	8.30	5.54
100w	19.93	9.97	6.64
1000w	23.25	11.63	7.75

2) Delete()

指定时间到达后，清除计时器。涉及 sift-down（下推）操作，时间复杂度为O(d * log n / log d)

Python代码

import math
result = d * math.log(n, d)

时间消耗（需要交换或者比较的次数）

n(数量)	二叉堆	四叉堆	八叉堆
1w	26.58	26.58	35.43
10w	33.33	33.33	44.29
100w	39.86	39.86	53.15
1000w	46.51	46.51	62.01

3. 结论

正常情况下，插入操作：多叉堆执行性能优于二叉堆; 删除操作：多叉堆执行性能弱于二叉堆。
但是细心的朋友应该已经发现，四叉堆插入操作的耗时只有二叉堆的一半，而删除操作的耗时与二叉堆完全相同。 这么一对比，优势确实显著。

参考资料

1.Heap (data structure)
2.Binary heap
3.d-ary heap
4.Golang 定时器底层实现深度剖析
5.数据结构：堆（Heap）

---