title: Running time of Prim's algorithm
body: <p>Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Prim's algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?</p>
  
  <pre><code>MST-PRIM(G,w,r)
  1.  for each u∈  G.V
  2.       u.key=inf
  3.       u.π=NIL
  4.  r.key=0
  5.  Q=G.V
  6.  while Q != Ø 
  7.     u=EXTRACT-MIN(Q)
  8.     for each v ∈  G.Adj[u]
  9.         if v∈  Q and w(u,v)&lt;v.key
  10.          v. π=u
  11.          v.key=w(u,v)
  </code></pre>
  
  <p>According to my textbook:</p>
  
  <p>The running time of Prim's algorithm depends on how we implement the min-priority queue Q. If we implement Q as a binary min-heap, we can use the BUILD-MIN-HEAP procedure to perform lines 1-5 in O(V) time. The body of the while-loop executes |V| times, and since each EXTRACT-MIN operation takes O(lg V) time, the total time for all calls to EXTRACT-MIN is O(VlgV). The for-loop in lines 8-11 executes O(E) times altogether, since the sum of the lengths of all adjacency lists is 2|E|. Within the for-loop, we can implement the test for membership in Q in line 9 in constant time by keeping a bit for each vertex that tells whether or not it is in Q, and updating the bit when the vertex is removed from Q. The assignment in line 11 involves an implicit DECREASE-KEY operation on the min-heap, which a binary min-heap supports in O(lg V) time. Thus, the total time for Prim's algorithm is O(V lg V+E lg V)=O(E lg V).</p>
  
  <p>The lines 1-4 require O(V) time. I have read some explanations why the BUILD-MIN-HEAP procedure requires linear time, but I haven't understood them. Could you explain  to me why the time complexity of the MIN-HEAP procedure is O(V)?</p>
  
  <p>Furthermore, I thought that at a min-heap, the minimum element is at the root. So, why does each EXTRACT-MIN operation take O(lg V) time?</p>
  
  <p>Then, the for-loop is executed O(Σ_{v in V.G} deg(v)) times, right? Could you explain me why Σ_{v in V.G} deg(v)=2E?</p>
  
  <p>Also, what would be different if we would know that the edge weights are integers in the range from 1 to W for some constant W?</p>
  
  <p><strong>EDIT</strong>:</p>
  
  <blockquote>
    <p>Suppose that all edge weights in a graph are integers in the range
    from 1 to |V|. How fast can you make Prim's algorithm run?</p>
  </blockquote>
  
  <p>What could we change at the above algorithm, so that the Prim's algorithm runs as fast as possible?</p>