Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$?
The pseudocode for Prim's algorithm, as stated in CLRS, is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V
2      u.key = ∞
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)


The loop in line 6 will execute exactly $|V|$ times, since $Q$ starts with $|V|$ elements and we remove one each iteration. For each node $u$, the loop in line 8 will execute $\text{deg}(u)$ times, so the DECREASE-KEY operation (lines 10 and 11) will execute at most $\text{deg}(u)$ times.

In total, the loop in line 8 will be executed $2|E| = \sum_{u \in G.V} \deg(u)$
times, and DECREASE-KEY $O(|E|)$ times.



I would suggest you to grab a piece of paper, draw a graph, and run the algorithm on it while counting how many times you do the DECREASE-KEY operation.