Why do we need a priority queue in Prim's Algorithm

Question

As my question speaks I want to know why do we use Priority queue in Prim's Algorithm? How does it saves us from using the naive way (yes I've heard of it but don't know why).

I'd be very happy if anyone could explain step by step for adjacency list . I am using Cormen's book.

The pseudocode :

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) < key[v]
                 then π[v] ← u
                       key[v] ← w(u,v)

I am thinking to use std::vector then std::make_heap(); as priority queue for storing edges.

Answer 1

In prim's algorithm, there is a step where you have to get the 'nearest' vertex. This step would cost O(N) if using normal array, but it'd take only O(logN) if you use priority queue (heap for example)

Hence, the reason for using priority queue is to reduce the algorithm's time complexity (which mean it make your program run faster)

**

Update:

**

Here is Prim's algorithm's description from Wikipedia. The bold part is the part for finding nearest vertex I talked about:

Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).

Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}

Repeat until Vnew = V: Choose an edge (u, v) with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked) Add v to Vnew, and (u, v) to Enew

Output: Vnew and Enew describe a minimal spanning tree

Answer 2

You don't "need" it. In fact, a naive implementation of Prim's algorithm would simply do a linear search of the array of distances to find the next nearest vertex. Dijkstra's algorithm works the exact same way.

The reason why people use it is because it significantly speeds up the runtime of the algorithm. It turns from O(V^2 + E) to O(E*log(V)).

The key to this is the EXTRACT-MIN(Q) function. If you do it naively, this operation would take O(V) time. With a heap, it only takes O(logV) time.