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)$