Union-Find Has Two Optimisations Because It Has Two Different Failures

Union-find answers one question — are these two things in the same group? — and it is the structure behind detecting cycles in a graph, finding connected components, building a minimum spanning tree, and any “did these two accounts turn out to be the same person” problem.

The structure itself is one array of integers. Every element points at a parent; each group is a tree; the element pointing at itself is the root that names the group. Looking something up means following pointers until you reach a root, so the cost of a lookup is exactly how deep that element sits. Everything interesting is about controlling that depth.

Two optimisations, two unrelated failures

The textbook presentation adds union by size, then adds path compression, and quotes a bound involving the inverse Ackermann function. What that ordering hides is that the two fixes are not cumulative refinements of the same idea. They rescue different disasters, and each is powerless against the other’s.

Toggle them independently, then merge one way and the other.

Chain order — join 0 to 1, then 1 to 2, then 2 to 3 — is the case union by size exists for. Without it, each merge hangs the growing tree under a fresh singleton and you end up with a thread. With it, a smaller tree can never adopt a larger one, so the singleton goes underneath and the depth stays at 1.

Pairwise order — join neighbours, then join the pairs, then the fours — is the case union by size cannot touch. At every merge the two trees are exactly the same size, so the rule has nothing to choose between them and depth grows logarithmically anyway. Path compression is what flattens that: once a lookup has paid to walk to the root, it re-points every node it passed straight at the root, so nobody pays for that walk twice.

All eight combinations

class UnionFind:
    """Each element points at a parent; the root of a tree names the set. `hops` counts every
    parent pointer followed, which is the only cost this structure has."""

    def __init__(self, n, by_size, compress):
        self.parent = list(range(n))
        self.size = [1] * n
        self.by_size = by_size
        self.compress = compress
        self.hops = 0

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
            self.hops += 1
        if self.compress:
            # Point everything on the path straight at the root, so the next find is one hop.
            while self.parent[x] != x:
                self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return
        if self.by_size and self.size[ra] > self.size[rb]:
            ra, rb = rb, ra          # always hang the smaller tree under the larger
        self.parent[ra] = rb
        self.size[rb] += self.size[ra]


def chain_order(n):
    """Join 0-1, then 1-2, then 2-3. Every union grows one long tree."""
    return [(i, i + 1) for i in range(n - 1)]


def pairwise_order(n):
    """Join neighbours, then join the pairs, then the fours. Balanced merging - what a real
    workload looks like, and the case union-by-size alone does NOT flatten."""
    pairs, step = [], 1
    while step < n:
        for i in range(0, n - step, step * 2):
            pairs.append((i, i + step))
        step *= 2
    return pairs


def deepest(uf):
    worst = 0
    for i in range(len(uf.parent)):
        d, cur = 0, i
        while uf.parent[cur] != cur:
            cur, d = uf.parent[cur], d + 1
        worst = max(worst, d)
    return worst


def run(n, order, by_size, compress):
    uf = UnionFind(n, by_size, compress)
    for a, b in order(n):
        uf.union(a, b)
    build = uf.hops
    for i in range(n):
        uf.find(i)
    return build, uf.hops - build, deepest(uf)


n = 1024
print(f"{'union order':<10} {'by size':>8} {'compress':>9} {'hops to build':>14} {'hops for 1024 finds':>20} {'depth after':>12}")
for name, order in [("chain", chain_order), ("pairwise", pairwise_order)]:
    for by_size in (False, True):
        for compress in (False, True):
            build, finds, depth = run(n, order, by_size, compress)
            print(f"{name:<10} {str(by_size):>8} {str(compress):>9} {build:>14,} {finds:>20,} {depth:>12}")

union order  by size  compress  hops to build  hops for 1024 finds  depth after
chain         False     False              0              523,776         1023
chain         False      True              0                2,045            1
chain          True     False          1,021                1,023            1
chain          True      True          1,021                1,023            1
pairwise      False     False          2,026                5,120           10
pairwise      False      True          1,532                2,028            1
pairwise       True     False          2,026                5,120           10
pairwise       True      True          1,532                2,028            1

Read the two blocks separately and the argument is unmissable.

In chain order, the unoptimised structure is a 1,023-deep thread costing 523,776 hops for 1,024 lookups — a linear scan, the same catastrophe as a search tree built from sorted input. Union by size takes it to 1,023 hops.

In pairwise order, look at rows five and seven. by size = False and by size = True give identical numbers — 2,026 hops to build, 5,120 to look up, depth 10. Union by size accomplishes precisely nothing here, because it never once has a larger tree and a smaller tree to choose between. Path compression takes those same lookups to 2,028 hops at depth 1.

That is why real implementations use both. Not because two optimisations are better than one, but because each one has a merge order that makes it irrelevant, and you do not get to choose the merge order — the problem does.

Why compression is nearly free

Path compression looks like it should cost something: it writes to every node on the path. But it only writes to nodes the lookup was already visiting, so it at most doubles the work of a walk that was happening anyway — and it does it once. Every future lookup of anything on that path is a single hop.

That is the pattern worth taking away, and it recurs: pay a small constant on the work you were already doing, in exchange for never doing it again. It is the same bargain as a dynamic array’s occasional expensive append, read from the other side.

What this page simplifies

• Union by size, not by rank. Rank tracks tree height instead of element count. They behave almost identically; rank stores a smaller number, size is easier to reason about.
• Depth, not the real bound. The famous result is that both optimisations together give an amortised cost that is inverse-Ackermann in n — smaller than 5 for any input that fits in the universe. This page counts hops on specific inputs instead, because a bound nobody can feel explains nothing.
• No deletion, no splitting. Groups only ever merge. Splitting a set again is a substantially harder problem and this structure cannot do it.
• Hops, not seconds. As everywhere in this cluster, pointer chasing also costs cache misses that these counts do not charge for.