CODEWITHSUNDEEP
algorithmheapbig-odijkstra
Shoggoth269
Shoggoth269

Reputation: 167

Big-O of Dijkstra's Algorithm with D-Ary Heap

I'm looking for a complete walkthrough on the runtime of Dijkstra's algorithm when implemented with a D-Ary heap.

My best understanding as of now is that the depth of the tree is at most log_d(n), so the max time of insertion and bubbling up is log_d(n). Wouldn't bubble down be the same on deleting a node?

I'm just having trouble piecing things together to find the total Big-O runtime here. My understanding is that it should be O(m logm/n n)), but I'd like to have a kind of walkthrough to understanding why that is the case.

Upvotes: 2

Views: 1707

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

In a d-ary heap, up-heaps (e.g., insert, decrease-key if you track heap nodes as they move around) take time O(log_d n) and down-heaps (e.g., delete-min) take time O(d log_d n), where n is the number of nodes. The reason that down-heaps are more expensive is that we have to find the minimum child to promote, whereas up-heaps just compare with the parent.

Assuming a connected graph, Dijkstra uses at most m - (n - 1) decrease-keys and at most n - 1 inserts/deletes (assuming that we never insert the root). The running time of Dijkstra using a d-ary heap as a priority queue is thus O((m + n d) log_d n), which is worth it for dense graphs.

Upvotes: 1

Related Questions