Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

Question

I am reading Prim's MST for the first time and wanted to implement the fast version of it .

$m$ - The number of edges in the graph

$n$ - The number of vertices in the graph

Here's the algorithm :

1) Create a Min Heap of size $V$ where $V$ is the number of vertices in the given graph. Every node of min heap contains vertex number and key value of the vertex.

2) Initialize Min Heap with first vertex as root (the key value assigned to first vertex is $0$ ). The key value assigned to all other vertices is $\infty$ .

3) While Min Heap is not empty, do following

…..a) Extract the min value node from Min Heap. Let the extracted vertex be u.

…..b) For every adjacent vertex $v$ of $u$, check if $v$ is in Min Heap (not yet included in MST). If $v$ is in Min Heap and its key value is more than weight of $u-v$, then update the key value of $v$ as weight of $u-v$.

Now my point is during implementation ( I am doing in C++) in step 3(b) I have to check whether the vertex is there in the heap or not . As we know , searching in a heap is done in $O(n)$ time . So in the main while loop which will run ( $n$ number of times ) although extract-min is $O(\log n)$ but the search ( whether $v$ is min heap or not takes time proportional to size of the heap ( although it is decreasing in each step ) .

So is it correct to say that the above algorithm is $O(m+n\log n)$

Answer 1

In your step 3b, you have to carry out at most $\deg(u)$ many decrease-key key operation. Thus in total you need $\sum \deg(u) = 2m$ many decrease-key operations. A single decrease key runs in $O(1)$ amortized time (Fibonacci Heaps). Thus the total running time is $O(m+n\log n)$. If you are not using Fibonacci heaps the running time is slower. Something like $O(m \log n )$.

I do not see how you got to $O(m+n\log n)$ by following your arguments. Also its unclear how you can do all the decrease-key key operation for one step in $O(n)$ time.