I'm reviewing my notes on Kruskal's algorithm and have a question about getting the runtime down to O(E lg V). By using a PQ with edges and a boolean array of which vertices we have added to our tree T, the running time is O(E lg E), but in my notes there is also a variant with running time O(E lg V), by using a PQ with vertices instead of edges. However, this requires the PQ to support updating weights (important part highlighted):
Maintain a PQ of vertices connected by an edge to T, togethether with the edge that connects it to T. The priority of this tuple is the weight of the min-weight edge connecting it to T. When adding a new vertex to the tree, we add all vertices adjacent to this new vertex to the PQ unless it's already in the PQ. If it is in the PQ and the new edge connecting it to T is of lower weight, we update its weight and the edge associated with it, if not, we do nothing.
When thinking about how to actually implement this, I realized that all priority queues I have seen have O(n) updates, since the ordering is too weak for us to be able to find an element faster. I tried searching a bit but couldn't find any PQs that support updating in O(lg n) time, except some references to fibonacci heaps that can do it in O(1) time, but looks like a much more complex data structure.
Is there a simple way to get O(lg n) updates of a priority queue? I could insert keys and references to elements in a hash table and use that to quickly find and update elements, is this a viable solution? (I realize that this will require O(n) extra space.)