# Is array implementation better or the min heap in case of Prims algorithm

1 vote
681 views
For prim's algorithm array implementation takes $O(V^2)$ while min heap implementation takes $O((E+V)\log V)$ time. For dense graph $E = O(V^2).$

So is array implementation considered better or the min heap one???

Does the min heap implementation run better for graph with less edges??

edited

For dense graph $E=O(V^2)$

Prim's Algorithm with Min heap takes $O((E+V)\log V)$ time

Array implementation takes $O(V^2)$

So, for dense graph

Min heap takes $O((V^2+V)\log V) = O(V^2 \log V)$ which is asymptotically more than $O(V^2)$

For sparse graphs, $E = O(V)$ and the time complexities for binary heap and array implementations will be $O(V \log V)$ and $O(V^2)$ respectively.

So, heap implementation is suitable for sparse graphs and array implementation for dense graphs.

selected by

## Related questions

1
1.7k views
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$