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.
Best How To :
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.