Prim's Algorithm - Building the Priority Queue

Question

Suppose we were using a priority queue (PQ) to implement Prim's algorithm. My understanding is that initially the weight of all vertices is set to $\infty$. The weight of the starting vertex is then set to $0$. All of the vertices are then inserted into the PQ.

1. Does that mean that we can insert the vertices in any order into the PQ?

2. Given that we can insert the vertices in any order, suppose we have a graph with the following vertices $a$, $b$ and $c$ and the following weights $w(a,b)=1$, $w(a,c)=2$. Once we set a.key = 0 and then extract a from PQ, we have b.key = 1 and c.key = 2. Given the answer to (1) was yes, my understanding would be that in a binary tree representation of the heap, $b$ would now be the root and $c$ would be a child of $b$. However, depending on the order in which the $a$, $b$ and $c$ were added to the heap, $c$ could be either the left or right child of $b$, right?

3. Suppose now that the graph has vertices $a$, $b$, $c$, $d$ and edges $(a, b)$, $(a, c)$, $(a, d)$. Suppose they were inserted into the heap in the order $a$, $b$, $c$, $d$. The binary tree representation of the heap should then be:
   $a$ is the root, $\operatorname{left}(a) = b$, $\operatorname{right}(a) = c$, $\operatorname{left}(b) = d$

So, that would mean that the parent-child relationships do not correspond to the parent-child relationships in the original graph and they don't have to, right?

Answer 1

1. Assuming your PQ is backed by a heap (as you refer to it later). Since the only invariant in a heap is that the parent must be $<$ the children (heap property) you can see there can be no ordering between children of a single parent. A priority queue will always return you the minimal element regardless of order, just think about how $\min$ works: $\min\{1,2,3\}=\min\{2,3,1\}=\min\{3,2,1\}$.

2. Because a heap is represented in a continous array, you'll have $[b, c]$ after removing $a$ which means that $c$ will always be the left child. Look at the heap image on Wikipedia and notice it's leaning left.

3. Yes, that's the order they'll be in a usual heap, because all their weights are $\infty$. But any other structure (regardless of insertion order) would be acceptable as long as $a$ is the root, because it wouldn't hurt the heap property.

parent-child relationships [in PQ's heap] do not correspond to the
parent-child relationships in the original graph

That is absolutely correct. Just because your PQ is backed by a heap which encodes a tree you can't assume that the graph structure will have anything to do with the heap tree's structure. Just think about a non-tree graph with cycles and multiple edges between vertices: how would that be reflected in the heap's tree? There isn't even a correspondence with the partial MST.

Another argument: the whole structure correspondence breaks big time as soon as you modify just one key in the heap and sift it to it's place. For example:

     a(0)                            a(0)
   b(∞) c(∞)   --- d.key = 1 -->   d(1) c(∞)
 d(∞)                             b(∞)

even before modifying the key $d$ was the child of $b$ which wasn't true in the graph and is not even reachable. The same is true after modification for the reverse.

---

The best is to think of a PQ as:

interface PriorityQueue {
    add(node, cost)
    update(node, cost)
    (node, cost) popMin()
}

the fact that it's implemented as a heap shouldn't be of a concern, just assume that the PQ does add and update in $\mathcal{O}(n\log{n})$ and popMin in $\mathcal{O}(1)$ to get quasilinear runtime of Prim's algorithm. Even when you implement it you should separate the algorithm from the PQ implementation.

Answer 2

Prim's algorithm considers edges in increasing cost, and once an edge is added (or not) it isn't considered again, and it's cost isn't changed at all. No need for a priority queue's complications, just sort and be done.