1回答

Xargin

2021-05-28

https://www.geeksforgeeks.org/k-ary-heap/

​

你看看上面这个链接，里面提到了多叉树的优点，和我上课说的也差不多：

• K-ary heap when used in the implementation of priority queue allows faster decrease key operation as compared to binary heap ( O(log2n)) for binary heap vs O(logkn) for K-ary heap). Nevertheless, it causes the complexity of extractMin() operation to increase to O(k log kn) as compared to the complexity of O(log2n) when using binary heaps for priority queue. This allows K-ary heap to be more efficient in algorithms where decrease priority operations are more common than extractMin() operation.Example: Dijkstra’s algorithm for single source shortest path and Prim’s algorithm for minimum spanning tree

• K-ary heap has better memory cache behaviour than a binary heap which allows them to run more quickly in practice, although it has a larger worst case running time of both extractMin() and delete() operation (both being O(k log kn) ).

1 的意思是虽然大家都是 logkn，但是多叉树的 k 要小，所以实际做堆调整的实际时间复杂度低一些

2 像 Go 里这个四叉，其实每个节点都保存了 4 个 timer，空间局部性比两叉好一些，对缓存友好(虽然实际上里面存的是指针，还是有二级寻址)

至于为什么是 4 叉，而不是 5 叉，6 叉。。我觉得可能没什么特殊考量，

这种设计的时候能是 2 的整数倍，能让树层数变少就行了

0