1

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.)

1
  • You can check Java implementation here.
    – Nine
    May 11, 2013 at 20:59

1 Answer 1

2

A simple binary heap can support O(log n) updating of an element if you have a pointer/reference to that element's position in the heap (which can be acquired through an auxillary hashtable if necessary). The O(log n) is actually due to the necessary work to preserve the heap property.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.