多叉堆

多叉堆

动机

使用优先队列实现的 Dijkstra 算法： 如果用二叉堆实现，时间复杂度为 $O((n+e)\log n)$

• 初始化 $O(n)$
• 每次取优先级最高的边 $O(\log n)$，共 $n$ 次，$O(n\log n)$
• 更新所有关联定点到 $u$ 的距离，共 $O(e\log n)$ 在稠密图中，$e$ 达到 $n^2$，此时时间复杂度退化到 $O(n^2\log n)$，比朴素实现更慢。 怎么解决？ 主要优化点在上滤，考虑降低上滤时间的同时略微增加下滤时间。

多叉堆

$parent(k)=\lfloor (k-1)/d\rfloor$ $child(k,i)=kd+i$ 仍可基于向量实现，

• 堆高降低至 ${\log }_{d}n$
• 上滤时间降低至 ${\log }_{d}n$
• 下滤需要遍历 $d$ 个孩子，时间为 $d{\log }_{d}n$，下滤 $d=3$ 时最小，之后反而增大 此时 Dijkstra 算法的时间成本为

$$n\cdot d{\log }_{d}n+e\cdot {\log }_{d}n$$

取 $d\approx e/n+2$ 时有最小值，时间复杂度为 $O(e\cdot {\log }_{e/2+2}n)$

• 对稀疏图保持高效，$O(n\log n)$，这是相对朴素实现的主要优化
• 对稠密图效率提高，$O(e)$