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

Question

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??

Answer 1

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.