I know Prim's algorithm and how to implement it. I am also aware of why its time complexity is O(E + V log(V)).
We add edges E times (that is in O(E)) and choose minimum V times (that is O(V*log(V)). But I don't understand a part of it: Why V times?! I know a tree has V-1 edges, but if the heaviest edge MUST be in MST, we have to choose the minimum E times, NOT V times.
For example: a complete graph with weight 1 for each edge, except one vertex that all of the edges connected to it are with weight 10^18.
You want to connect V vertices using edges from your initial graph, making a tree. You can start from any node, let's say v. Then you add to your queue all vertices that you can reach from v with the cost of the edge connecting it. You go to the one with the cheapest cost. Now you do the same thing. If you want to put in your queue vertex u, that already is in your queue, you have to check the wage on it's edge. If the new one is smaller, you take out the older one and insert the newer, if not, you skip it. Also, if you have already connected node u to your tree, you also skip it. So there will be at most V vertices in your queue, making the time complexity O (E + V log V) (E - because you have to check all edges for every vertex)
EDIT: To be more specific, when you add vertex u again to the queue, you can either erase the previous one, or just change it's cost. The other thing should be faster if you use Fibonacci heaps. Deletion will cost you O(E log V) instead of O(E + VlogV)