我正在寻找有关使用 D-Ary 堆实现 Dijkstra 算法运行时的完整演练。
目前我最好的理解是树的深度最多是log_d(n)，所以插入和冒泡的最大时间是log_d(n)。删除节点时冒泡不是一样吗？
我只是无法将所有东西拼凑在一起以在此处找到总的 Big-O 运行时。我的理解是它应该是 O(m logm/n n))，但我想通过一种演练来理解为什么会这样。
最佳答案
在 d 元堆中，上堆(例如，如果您跟踪堆节点移动时插入、减少键)需要时间 O(log_d n)，而下堆(例如，delete-min)需要时间时间 O(d log_d n)，其中 n 是节点数。 down-heaps 更昂贵的原因是我们必须找到最小的 child 来提升，而 up-heaps 只是与 parent 比较。
假设一个连通图，Dijkstra 最多使用 m - (n - 1) 个减少键和最多 n - 1 个插入/删除(假设我们从不插入根)。 Dijkstra 使用 d 元堆作为优先级队列的运行时间因此为 O((m + n d) log_d n)，这对于密集图来说是值得的。
关于algorithm - Dijkstra 算法的大 O 与 D-Ary 堆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30080265/