Prim's algorithm computes a minimum spanning tree when edges have
arbitrary weights.

Prim's algorithm works by doing a sort of breadth-first search, starting
from some arbitrary node, and keeping the edges in a priority queue. It
keeps extracting the lowest-weight edge and either discarding it without
expanding the search (if the edge leads to a node already in the tree) or
adding it to the result, marking its opposite node as in the tree, and
expanding the search.

Done in the naive way I just explained, Prim's algorithm is dominated by
the cost of enqueueing and dequeueing `|E|`

edges into/outof the
priority queue. Each enqueue/dequeue takes `O(log |E|)`

time, so
the total asymptotic cost is `O(|E| log |E|)`

time or, more
properly, `O(|E| log |E| + |V|)`

.

If we had some way to do those enqueues and dequeues in constant time,
the total running time would be `O(|E| + |V|)`

...