A dd-ary min heap with nn elements has the following time complexity:

  • Insertion. O((log⁡n)/(log⁡d))O\big((\log n) / (\log d) \big).
  • Extract-Min. O(d⋅(log⁡n)/(log⁡d))O\big(d \cdot (\log n) / (\log d) \big).
  • Decrease-Key. O((log⁡n)/(log⁡d))O\big((\log n) / (\log d) \big).

Recall that for a single source shortest path query on a graph with nn vertices and mm edges, the Dijkstra's Algorithm performs nn extract-min operations, and mm decrease-key operation. Working with dd-ary min heap, it has time complexity

O(n⋅d⋅log⁡nlog⁡d+m⋅log⁡nlog⁡d) O \left( n \cdot d \cdot \frac{\log n}{\log d} + m \cdot \frac{\log n}{\log d} \right)

Setting d=m/nd = m / n minimizes this to

O(m⋅log⁡m/nn)=O(m⋅log⁡nlog⁡(m/n)). O \left( m \cdot \log_{m / n} n \right) = O \left( m \cdot \frac{\log n}{\log (m / n)} \right).

Consider the following cases:

  • m=O(n)m = O(n), then the time complexity is O(nlog⁡n)O(n \log n).

  • m=Θ(nlog⁡n)m = \Theta (n \log n), then the time complexity is

    O(n⋅(log⁡n)⋅log⁡nlog⁡log⁡n). O \left( n \cdot (\log n) \cdot \frac{\log n}{\log \log n } \right).

    Example:

    1. when n=220=1n = 2^{20} = 1M, (log⁡n)/(log⁡log⁡n)=20/(log⁡20)≈4.6(\log n) / (\log \log n) = 20 / (\log 20) \approx 4.6.
    2. when n=230=1n = 2^{30} = 1G, (log⁡n)/(log⁡log⁡n)=30/(log⁡20)≈6.1(\log n) / (\log \log n) = 30 / (\log 20) \approx 6.1.

  • m=Θ(n1+ϵ)m = \Theta \big( n^{1 + \epsilon} \big) for some ϵ>0\epsilon > 0, then the time complexity is

    O(mϵ). O \left( \frac{m}{\epsilon} \right).