When to use array and priority queue respectively for Prim's algorithm?

Question

This is an old exam question.

Under what condition on (V, E) should we implement the min-priority queue of Prim's algorithm using an array (indexed by the vertices) rather than a heap (with logarithmic-time implementations of both the Extract-Min and Decrease-Key operations)?

Under what condition on (V, E) should we implement the min-priority queue of Prim's algorithm using an ordered array?

Answer 1

When E is large, it's better to use a heap for the priority queue as we will have many nodes in the queue. It will take time to find min/remove min from an array O(n)/O(n), while a heap only takes O(1)/log(n).

If E is small, we will have few nodes in the queue and thus, to find min and remove it from the array will not need a lot of operations in this case. In this using a heap will not be necessary and it might even be slower than an array due to operations needed to build the heap.

Answer 2

Prim's runs in O(mlog(n)) time with the binary heap implementation and m being the # of edges and n being the # of vertices. However, when a graph is very dense, m is very large, then Prim's runs in O(n^2log(n)) . You can create a graph with a large number(n) of vertices and connect all the vertices to each other to convince yourself of this. so.... (n-1) + (n-2) + (n-3) ...... (n-n+1).

This can be re written as

n(n+1)/2 which is O(n^2) as documented on

the priority queue array implementation runs in O(n^2) time which is documented on the wikipedia page here, although I don't have a proof for it.

So it is better to use the adjacency matrix when m very large.

You asked for a condition and I would say when m is very large and the same order as n.