title: Why do we need a priority queue in Prim's Algorithm
body: <p>As my question speaks I want to know why do we use Priority queue in <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Prim%27s_algorithm" rel="nofollow">Prim's Algorithm</a>?
  How does it saves us from using the naive way (yes I've heard of it but don't know why).</p>
  
  <p>I'd be very happy if anyone could explain step by step for adjacency list . I am using Cormen's book.</p>
  
  <p>The pseudocode :</p>
  
  <pre><code>Prim(G,w,r) //what is w (weight?) and r?
    For each u in V[G]
      do key[u] ← ∞ // what is key?
         π[u] ← NIL  
    key[r] ← 0
    Q ← V[G]  
    While Q ≠ Ø
      do u ← EXTRACT-MIN(Q)
         for each v in Adj[u]
              if v is in Q and w(u,v) &lt; key[v]
                   then π[v] ← u
                         key[v] ← w(u,v)
  </code></pre>
  
  <p>I am thinking to use std::vector then std::make_heap(); as priority queue for storing edges.</p>