Union-find approach - weighted quick-union - jaredgorski.org

Back to notes

Union-find approach - weighted quick-union

Keywords: union-find, quick-union, algorithms
Date:

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!

Backlinks: