Union-Find
Quick-find [Eager approach]
Data Structure
- Integer array id[] of size N.
- Interpretation: p and q are connected iff they have the same id
Find
Check if p and q have the same id.
1 | ie. |
Union
To merge components containing p and q, change all entries whose id equals id[p] to id[q]
Implementation
1 | public class QuickFindUF { |
Efficiency
Cost model: Number of array accesses (for read or write)
Algogrthim | Initialize | Union | Find |
---|---|---|---|
Quick-find | N | N | 1 |
Quick-find defect:
Union too expensive.
Trees are flat, but too expensive to keep them flat
Takes $N^2$ array accesses to process sequence of $N$ union commands on $N$ objects
Quick Union [Lazy Approach]
Data Structure
- Integer array id[] of size N.
- Interpretation: id[] is parent of i.
- Root of i is id[id[id[…id[i]…]]] <- (keep going until it doesn’t change (Algorithm ensures no cycles))
Find
Check if p and q have the same root
Union
To merge components containing p and q, set the id of p’s root to the id of q’s root.
Implementation
1 | public class QuickUnionUF { |
Efficiency
Cost model: Number of array accesses (for read or write)
Algogrthim | Initialize | Union | Find |
---|---|---|---|
Quick-union | N | N* | N <- worst case |
ps: * includes cost of finding roots
Quick-union defect:
- Trees can get tall
- Find too expensive (could be N array access)
Improvement 1 - Weighting
Weighted quick-union
- Modify quick-union to avoid tall trees.
- Keep track of size of each tree (Number of objects)
- Balance by linking root of smaller tree to root of larger tree.
Data Structure
- Same as quick-union, but maintain extra array sz[i] to count number of objects in the tree rooted at i.
Find
Identical to quick-union
Union
Modify quick-union to:
- Link root of smaller tree to root of larger tree
- Update the sz[] array.
Implementation
1 | public class WeightedQuickUnionUF { |
Efficiency
Running Time:
- Find: takes time proportional to depth of p and q
- Union: takes constant time, given roots.
Algogrthim | Initialize | Union | Find |
---|---|---|---|
Weighted QU | N | lgN * | lgN |
ps: * includes cost of finding roots
Improvement 2 - Path Compression
Quick Union with path compression
- Just after computing the root of p, set the id of each examined node to point to that root.
Implementation
1 | // Two pass: add second loop to root() to set the id[] |
Note:
Linear-time algorithm for M union-find ops on N objects?
- Cost within constant factor of reading in the data.
- In theory, WQUPC is not quite linear.
- In practice, WQUPC is linear.
Summary
Legend: M union-find operations on a set of N objects
Algogrthim | worst-case-time |
---|---|
quick-find | M N |
quick-union | M N |
Weighted QU | N + MlogN |
QU + Path Compression | N + MlogN |
Weighted QU + Path Compression | N + Mlg*N |
- note: lg*N means the number makes lgN to 1. (inverse Ackerman function)