algorithm - Dijkstra算法复杂度分析误区

给出了Cormen book中的以下算法：

DIJKSTRA(G,w,s)

1. INITIALIZE-SINGLE-SOURCE(G,s)
2. S <-- {0}
3. Q <-- V[G]
4. while (Q != {0})
5.    do u <-- extract-min(Q)
6.    s <-- s U {u}
7.    for each vertex v at Adj(u)
8.            do RELAX(u,v,w)



RELAX (u,v,w)
if d[v] > d[u] + w(u,v)
    then d[v] <-- d[u] + w(u,v)
       pie(v) <--- u

我们的教授告诉我们，如果使用二进制堆，Relax操作需要O（log | V |），因此
第7-8行的循环取o（e*log v）。（如果我们使用线性队列，那么relax取o（1））。
我在谷歌上搜索了一段时间，却找不到一个好的解释。
当我们使用二进制堆时，为什么relax操作采用o（log v）呢？
希望能得到帮助谢谢。

最佳答案

在Relax函数中，d[v]处的键值被更新，我们需要再次维护最小堆，因为它可能违反平均堆的属性，所以整个Relax过程需要O（logv）时间保持最小堆并准备提取下一个最小值。

RELAX (u,v,w)
if d[v] > d[u] + w(u,v)
    then d[v] <-- d[u] + w(u,v)        //* updation.
       pie(v) <--- u