· Development

Union-find path compression and weighting: which implementation the α(n) bound belongs to

How size weighting, path compression and path halving change a union-find parent array, and which bound, worst-case Θ(log n) or O(m α(n)) per sequence, algs4 gives each implementation.

DevelopmentAlgorithmsData structures

Union-find (disjoint sets) is often summed up as “practically O(1)” or “O(α(n)) per operation”. That claim comes with conditions. The implementation has to combine weighting (by size or rank) with path compression, and the bound covers a whole sequence of operations starting from an empty structure, not any single operation. The implementation docs on the official site for Sedgewick and Wayne’s Algorithms, 4th Edition (algs4) say that even with both techniques, a single union or find takes Θ(log n) time in the worst case.

Below, using four algs4 implementations, I separate what each technique does to the parent array and which complexity statement belongs to which implementation.

The parent array and find

Quick-union style implementations store, for each element, another element of the same set (or itself) in parent[i]. An element with parent[i] == i is a root, and find follows links up to the root. Two elements are in the same set if they reach the same root. Union finds both roots and links one under the other.

So the cost of find depends on how deep the starting node is. Section 1.5 of algs4 counts cost in array accesses and states as a proposition that find in quick-union uses 1 plus twice the depth of the node. Every technique below is a way of keeping that depth down.

Size weighting: smaller tree under the larger

Plain quick-union doesn’t choose which root goes under which. Call union(i, i+1) for i = 0, 1, … on n elements, and algs4’s QuickUnionPathCompressionUF (id[rootP] = rootQ) builds a chain 0 → 1 → … → n−1. Each find in that sequence starts at a root, so there is no path to compress, and element 0 ends up at depth n−1.

WeightedQuickUnionUF records each tree’s element count in size[] and links the root of the smaller tree under the root of the larger one.

if (size[rootP] < size[rootQ]) { parent[rootP] = rootQ; size[rootQ] += size[rootP]; }
else                           { parent[rootQ] = rootP; size[rootP] += size[rootQ]; }

On a tie the else branch runs and q’s root goes under p’s root. Feed this implementation the same union(i, i+1) sequence and every element lands directly under 0, for a maximum depth of 1.

For weighted quick-union, algs4 gives a proposition that no node in a forest built from n sites is deeper than lg n, and a corollary that the worst-case order of growth of find, connected and union is log n. Both statements are about the implementation without path compression, and both are worst-case bounds on each individual operation.

Here it is with 8 elements, 0 to 7.

Call parent[0..7] size change
start 0 1 2 3 4 5 6 7 all 1
union(0,1) 0 0 2 3 4 5 6 7 size[0]=2
union(2,3) 0 0 2 2 4 5 6 7 size[2]=2
union(0,2) 0 0 0 2 4 5 6 7 size[0]=4
union(4,5) 0 0 0 2 4 4 6 7 size[4]=2
union(6,7) 0 0 0 2 4 4 6 6 size[6]=2
union(4,6) 0 0 0 2 4 4 4 6 size[4]=4
union(0,4) 0 0 0 2 0 4 4 6 size[0]=8

The final size array is 8 1 2 1 4 1 2 1. From 7 to the root is 7 → 6 → 4 → 0, three links, exactly lg 8. Every union merged two trees of equal size, which is why this example hits the bound. Each find inside those seven unions started at a root, so an implementation with path compression ends up with exactly the same array.

Section 1.5 notes that ideally every node would link directly to its root, but we don’t want to pay for changing a large number of links. The approach it describes is to link only the nodes find actually examines. Find in WeightedQuickUnionPathCompressionUF makes two passes: one to find the root, one to relink each node on the path to it.

int root = p;
while (root != parent[root]) root = parent[root];
while (p != root) { int newp = parent[p]; parent[p] = root; p = newp; }
return root;

Calling find(7) on the state above follows three links to reach root 0 in the first loop, and the second loop links 7, 6 and 4 directly to 0.

parent[0..7]
before find(7) 0 0 0 2 0 4 4 6
after find(7), full compression 0 0 0 2 0 4 0 0

A few things to notice.

  • This find still followed three links. Compression makes the next find cheaper. It doesn’t shorten the current one. That is why the algs4 docs still list union and find as Θ(log n) in the worst case for this implementation.
  • The root doesn’t change. The algs4 docs say a set’s canonical element can change only when the set itself changes during union, never during find. Compression only reshapes the tree.
  • size[] isn’t updated. After compression only 5 is left under 4, yet size[4] is still 4. The source comment says size is not necessarily correct when i isn’t a root. Union only compares size[rootP] and size[rootQ], the values at roots, so nothing breaks. Compression never moves an element into another tree, so a root’s size is still the number of elements in its set.

UF, the class whose main() Section 1.5 uses to solve its dynamic connectivity example, uses a different pair: weighting by rank instead of size, and path compression by halving.

while (p != parent[p]) {
    parent[p] = parent[parent[p]];
    p = parent[p];
}
return p;

In one pass, each node it visits is linked to its grandparent, and the walk then jumps to that grandparent. Only every other node on the path gets changed. Run the same seven unions through UF and, since every union in this example joins two trees of equal rank, the parent array matches the size-weighted one; the ranks end up as 3 0 1 0 2 0 1 0. Now find(7) gives a different result.

parent[0..7]
before find(7) 0 0 0 2 0 4 4 6
after find(7), path halving 0 0 0 2 0 4 4 4

7 moves up to its grandparent 4. Node 4’s grandparent is already 0, so it stays put, and 6 is skipped over and left alone. The tree doesn’t flatten in one go the way full compression does; call find(7) again and 7 moves to 0. In exchange it needs only the one loop that finds the root, and a web exercise in Section 1.5 introduces path halving as a simpler strategy.

Which statement goes with which implementation

The table restates what the algs4 class docs and the Section 1.5 text say.

Implementation Weighting Path compression Single operation (worst case) Whole sequence
WeightedQuickUnionUF size none union, find Θ(log n); depth ≤ lg n is a proposition in the text not stated
QuickUnionPathCompressionUF none full not stated union, find, connected in logarithmic amortized time
WeightedQuickUnionPathCompressionUF size full union, find Θ(log n) O(m α(n)) for m operations
UF rank halving union, find Θ(log n) O(m α(n)) for m operations

The exact condition for O(m α(n)) is this: starting from an empty structure with n sites, any intermixed sequence of m union and find operations takes O(m α(n)) time in total, where α(n) is the inverse of Ackermann’s function. “α(n) per operation” is that total divided by m, an amortized cost. No assumption about random input goes into it. If amortized analysis is new to you, why appending to a dynamic array is O(1) walks through the same kind of argument.

What the sources actually establish

It’s worth separating the forms these figures take in the algs4 material.

  • Depth ≤ lg n and the log n worst case are a proposition and corollary in the Section 1.5 text.
  • That path compression without weighting has logarithmic amortized cost, and that weighting plus path compression has amortized cost bounded by the inverse Ackermann function, appear only as notes to Exercises 1.5.12 and 1.5.13, phrased as “known”. The note on 1.5.13 adds that the value is less than 5 for any conceivable n that arises in practice.
  • O(m α(n)) is a sentence in the class docs of WeightedQuickUnionPathCompressionUF and UF.

None of the material I opened proves the α(n) bound, and I didn’t check the original paper. So this post doesn’t compare rank against size, or halving against full compression, on speed. The table only goes as far as the algs4 docs go for each implementation.

Sources

All checked on 2026-10-18.

Back to the blog