Union-find approach - weighted quick-union

• 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 of p and q
  • 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 the id 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 the id[] of each visited node to the root
  • “one-pass” (simpler):
    • make every other node in the path point to its grandparent (cuts the path length in half)
• 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!