四叉堆

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://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. 结论 正常情况下，插入操作：多叉堆执行性能优于二叉堆; 删除操作：多叉堆执行性能弱于二叉堆。 但是细心的朋友应该已经发现，四叉堆插入操作的耗时只有二叉堆的一半，而删除操作的耗时与二叉堆完全相同。 这么一对比，优势确实显著。 ...