Prim's Algorithm with Treaps

Question

Can Prim's algorithm be implemented by treaps to speed up the execution because a normal heap would pose a problem in updating the value of keys while storing vertices in heaps which otherwise would require O(V) space to store location of vertices in heap?

Answer 1

This will not necessarily make Prim's algorithm any faster. Consider the following degenerate case - you have n nodes v1, v2, ..., vn, and their priorities are such that p(v1) < p(v2) < p(v3) < ... < p(vn). In that case, the treap will be a degenerate linked list, and if you need to update priorities along the way, simply looking up the nodes in the tree might take time Ω(n). A standard binary heap with an extra lookup table would be faster than this.

Sorry for the negative result, but I hope this helps!