Dijkstra的D-Ary堆算法的大O

Question

我正在寻找一个完整的Dijkstra算法的运行时演练，当用D-Ary堆实现时。

我现在最好的理解是树的深度至多是log_d（n），所以插入和冒泡的最大时间是log_d（n）。在删除一个节点时不会冒泡？

我只是无法将事物拼凑在一起，在这里找到总的Big-O运行时。我的理解是它应该是O（m logm/n n）），但我希望有一种演练来理解为什么会这样。

Answer 1

在d-ary堆中，上堆（例如，插入，如果跟踪堆节点移动时减少键）需要时间O（log_d n）和下堆（例如，删除最小值）花费时间O（d log_d n），其中n是节点的数量。下堆更昂贵的原因是我们必须找到最小的孩子来提升，而上堆只是与父母比较。假设连接图，Dijkstra最多使用m - （n - 1）个减少键，最多使用n - 1个插入/删除（假设我们从不插入根）。 Dijkstra使用d-ary堆作为优先级队列的运行时间因此是O（（m + n d）log_d n），这对于密集图是值得的。