Algorithm, Part I — Union-find with specific canonical element

Q: Add a method find() to the union-find data type so that find(i) returns the largest element in the connected component containing i. The operations, union()connected(), and find() should all take logarithmic time or better.

For example, if one of the connected components is {1,2,6,9}, then the find() method should return 9 for each of the four elements in the connected components.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

The approach is similar to the one for the previous post. Let’s first look at some naive solutions.

1. If we implement the naive union-find as the base algorithm, the find() method would require O(N) time since we have to linearly scan all elements in the same component. So this is not acceptable.

2. So how about using the weighted quick union-find as the base? Where do we go next? Well, a connected component is represented by a tree. We could find the root of an object in O(logN) time and then use a breadth-first search to scan all objects in the tree to find the max. Unfortunately that’s not efficient enough.

3. As I mentioned, we use a similar approach–that is to keep track of things along the way of the union operations. Can we keep track of the max object in a given component and update it when doing union? In that way find() will only take constant time and the other methods will have the same time cost as before.

Well I guess we can. Code  on github:

Enhanced by Zemanta
Advertisements

3 thoughts on “Algorithm, Part I — Union-find with specific canonical element

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s