Union-find approach - weighted quick-union
Keywords: | union-find, quick-union, algorithms |
Date: |
- Weighted quick-union is a modification to quick-union that helps by avoiding the problem of tall trees
- track the size of each tree (number of objects)
- balance by linking the root of the smaller tree to the root of the larger tree (union by size on a disjoint-set)
- alternatively use union by height/rank
Example implementation
The only difference between this and quick-union is the addition of the sz[]
array, which counts the number of objects in the tree rooted at i
public class WeightedQuickUnionUF
{
private int[] id;
private int[] sz;
public WeightedQuickUnionUF(int N)
{
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++)
{
id[i] = i;
sz[i] = 1;
}
}
private int root(int i)
{
while(i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q)
{
return root(p) == root(q);
}
public void union(int p, int q)
{
int i = root(p);
int j = root(q);
if (i == j) return;
if (sz[i] < sz[j])
{
id[i] = j;
sz[j] += sz[i];
} else
{
id[j] = i;
sz[i] += sz[j];
}
}
}
- This approach improves upon quick-union:
Find
: time is proportional to depth ofp
andq
Union
: constant time, given roots
- the depth of the tree will always be equal to or less than
log2 N
Cost:
new
:N
Union
:log2 N
(including cost of finding roots)Find
:log2 N
Another improvement: path compression
- upon computing
root(p)
, simply set theid
of each visited node to point to that root - this lets us circumvent the internal cost of
root()
by essentially memoizing the operation - Implementations:
- "two-pass":
- add second loop to
root()
to set theid[]
of each visited node to the root
- add second loop to
- "one-pass" (simpler):
- make every other node in the path point to its grandparent (cuts the path length in half)
- "two-pass":
- both implementations let us keep the tree flat, which makes things easier
- cost is improved dramatically to near linear-time
- with path-compression, weighted quick-union allows 10^9 unions on 10^9 objects to be executed in 6 seconds
- shows the value of a good algorithm!
- with path-compression, weighted quick-union allows 10^9 unions on 10^9 objects to be executed in 6 seconds