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.
Does that mean that we can insert the vertices in any order into the PQ?
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 haveb.key = 1
andc.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?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?