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?
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!