Ideal value of d in a d-ary heap for Dijkstra's algorithm

Question

I stumbled upon the following statement:

By using a $ d $-ary heap with $ d = m/n $, the total times for these two types of operations may be balanced against each other, leading to a total time of $ O(m \log_{m/n} n) $ for the algorithm, an improvement over the $ O(m \log n) $ running time of binary heap versions of these algorithms whenever the number of edges is significantly larger than the number of vertices

Applications of d-ary heaps

I don't understand why we choose to have a heap where nodes have exactly $ m/n $ children to speed up Dijkstra's algorithm. Remove min takes overall $ O(n \log_d n) $ time and decrease takes $ O(m \log_d n) $, so total runtime is $ O(m \log_d n) $.

What I don't understand is say we have $ m=3, n=1 $, $ m/n $ gives 3, but $ O(m \log_3 n) $ is slower than $ O(m \log_4 n) $, so why not choose 4 as value of $ d $ instead? What motivates taking $ m/n $?

Thanks!

Answer 1

whenever the number of edges is significantly larger than the number of vertices

What they probably mean is that $m \in \omega(n)$. Then, $m/n \in \omega(1)$ -- the base of the logarithm grows with $n$, that is the resulting sequence of values grows more slowly than with a fixed base.

For dense graphs in the sense that $m \in \Theta(n^2)$, the effect is most pronounced. For the sake of simplicity, say $m = cn^2$ for some $c \in (0,1)$. Then, $m/n = cn$ and therewith $\log_{m/n} n = \log_{cn} n \in O(1)$ -- the logarithmic factor has vanished, the algorithm has running-time in $O(m)$.

Note that all of this is discussing only the upper Landau-bound. In which way the true running-time cost is affected by this change is not per se clear, and the Wikipedia article is bold in claiming that it's an "improvement".

Answer 2

Please note that $ m \leq n(n-1)/2 $, thus $m/n < n/2$. So the example $m=3, n=1$ does not happen.

First, the article clearly claims that this improvement is achieved whenever $ m $ is larger than $ n $,

By using a $d$-ary heap with $d = m/n$, ..., an improvement over the O(m log n) running time of binary heap versions of these algorithms whenever the number of edges is significantly larger than the number of vertices.

Secondly, the article claims that $d$ must create a balance between $m$ and $n$ in order to improve the running time,

By using a $d$-ary heap with $d = m/n$, the total times for these two types of operations may be balanced against each other...

Generally, we need $n$ min-extract and $m$ decrease-key operations. In the case of $d=2$, each of these operations takes $O(\log n)$ time. However, when you increase $d$, the decrease-key operation becomes faster, but min-extract can become slower. Because, within each min-extract, we also need to run min-heapify that depends on the number of children of the parent in each level.

In the extreme case, if you consider $ d=n $ then $m \log_n n < m \log_{m/n} n$, but the running time won't be better in practice. Because you need at most $ n $ min-extract operations, each includes a min-heapify. Therefore, you need $ n $ min-heapify operations, that will cost $ O(n) $ in this case (because $d=n$ and there are $n$ numbers in the next level of your tree). Thus the running time of your algorithms becomes $O(n^2)$ ($n$ times running min-heapify).

Answer 3

Runtime of Dijkstra with $n$ nodes and $m$ edges and using a $d$-ary heap for the priority queue will be $O((nd+m)\log_d n)$:

• $O(nd\log_d n)$ from ExtractMin operations and
• $O(m\log_d n)$ from ChangePriority (strictly DecreaseKey) operations.

We want to balance $nd$ against $m$, given $m\gg n$. I.e. $nd=m$, or, $d=m/n$. If we have a constant $d$, asymptotic time will lean towards $O(m)$ [$m\gg n$].

In practice you'll need to play around a little to know what value of $d$ works for you.