Programming

Union–Find

Begin with a universe of isolated atoms. Every merge is an irreversible climb up a crystal mountain that can never be descended. By the summit, the cost of each step is governed by the slowest-growing function in human mathematics.

Rewrite every block label in 31.7 years, or climb the partition lattice in 4 seconds with the Ackermann bound.

Mission 01about 13 min

Fuse isolated nodes into cohesive components and flatten lookup paths to the nearly constant Ackermann bound.

  1. Step the lattice climb to watch single merges fuse partition blocks
  2. Deposit potential tokens on parent pointers before running find
  3. Trigger path compression to collapse tree depth down to α(n)

After thisYou can track dynamic connectivity across millions of nodes in constant amortised time.

Short on timeThe PotentialBank interactive panel in §4

Six Atoms on a Table

3 minthe hook

Relabelling the block you merge into is the obvious implementation, and at it writes labels. At a billion writes a second that is 31.7 years. Union by rank with path compression walks parent pointers and finishes in 4 seconds.

Six isolated elements sit on the table in front of you. Press merge, and two of them collapse into a single bonded clump that can never be pulled apart.

The picture is the lattice: nodes are the partitions of the set, cover edges are single merges, and the climb only goes up.

You start with 1,000 isolated elements and run 3,000 random union requests. At most, how many of those operations can actually alter the partition?

NextWhy does storing the set answer directly trigger a quadratic explosion?

The Trap of Storing Answers

2 minthe trap

Fix a finite set S of n elements. You will be asked, over and over, two questions: are x and y in the same block, and can you merge the block of x with the block of y. A first course calls this “disjoint sets” and moves on.

The naive answers are worse than they look. Keep a label array and relabel every member of the block you merge into — typically the larger one: one merge can cost Θ(n), so a sequence of n merges costs Θ(n²).

Keep a member list per set and copy the longer list on each merge: the same trap, the same quadratic. Relabelling the smaller block instead is a real repair and costs O(n log n) over n merges, but it still keeps a label per element rather than the partition. Neither method is slow because the idea is bad; both are slow because they store the answer instead of the partition.

NextHow does the partition lattice guarantee merges can never be reversed?

The Lattice You Cannot Descend

2 minthe invariant

The state is a partition π of S: a set of non-empty, pairwise disjoint blocks whose union is S. find reads the block containing an element; merge fuses two blocks. Nothing else is ever stored.

Partitions of a fixed set are partially ordered by refinement: π refines σ when every block of π lies inside a block of σ.

Under that order the partitions form a lattice, the partition lattice , which is graded and semimodular (Birkhoff, Lattice Theory, 1940). The bottom is all singletons, the top is the single block S, the meet is the common refinement, and the join has as blocks the connected components of the graph joining elements that share a block in π or in σ.

A merge(a, b) is not a new operation. It is the join with the two-block partition that puts a and b together:

Only two blocks move, so the join is just “fuse block(a) with block(b)”. And because a join can only fuse, every run of merges is a monotone climb up the lattice — it can never come back down. Since the two-block partition has rank 1, joining with it either fuses two blocks, a single cover step, or fuses nothing, when a and b already share a block.

Now the number you would have written into the code as a counter:

The lattice rank and the merge counter are the same number. A runtime statistic is a coordinate of where the state sits in an order-theoretic diagram.

Watch the gold path, not the drawing: when you click a pair from different blocks, one cover edge is taken and the block count falls by exactly one. That fall is the invariant, and it is the same quantity as the merge counter.

Climb: 123|4 → 1234Climb: 124|3 → 1234Climb: 12|34 → 1234Climb: 12|3|4 → 123|4Climb: 12|3|4 → 124|3Climb: 12|3|4 → 12|34Climb: 134|2 → 1234Climb: 13|24 → 1234Climb: 13|2|4 → 123|4Climb: 13|2|4 → 134|2Climb: 13|2|4 → 13|24Climb: 14|23 → 1234Climb: 1|234 → 1234Climb: 1|23|4 → 123|4Climb: 1|23|4 → 14|23Climb: 1|23|4 → 1|234Climb: 14|2|3 → 124|3Climb: 14|2|3 → 134|2Climb: 14|2|3 → 14|23Climb: 1|24|3 → 124|3Climb: 1|24|3 → 13|24Climb: 1|24|3 → 1|234Climb: 1|2|34 → 12|34Climb: 1|2|34 → 134|2Climb: 1|2|34 → 1|234Climb: 1|2|3|4 → 12|3|4Climb: 1|2|3|4 → 13|2|4Climb: 1|2|3|4 → 14|2|3Climb: 1|2|3|4 → 1|23|4Climb: 1|2|3|4 → 1|24|3Climb: 1|2|3|4 → 1|2|3412341234123|4123|4124|3124|312|3412|34134|2134|213|2413|2414|2314|231|2341|23412|3|412|3|413|2|413|2|414|2|314|2|31|23|41|23|41|24|31|24|31|2|341|2|341|2|3|41|2|3|4
selected: 1|2|3|4blocks: 4 of 4climb from bottom: 0hover a node to see its join with the selection

Partitions of {1,2,3,4} by refinement. The gold path runs from the bottom (four singletons) to the top (one block). Each upward cover edge fuses exactly two blocks. Click a pair of elements to take the join.

For n = 4 the diagram has 15 nodes, the Bell number , and 31 cover edges. “Reachable above” the current partition is : from the bottom, every partition of four objects is still ahead of you. Nothing autoplays here — the climb is yours to drive.

NextHow do physicist tokens pay for the tree-flattening steps ahead of time?

The Physicist’s Bank Account

2 minthe algebra

Two facts carry the page.

Fact 1 — equivalence relations are partitions. A relation on S that is reflexive, symmetric and transitive splits S into its classes, and every partition of S arises from exactly one such relation. That correspondence is exact: the fibres of find are the blocks. Union–Find is not computing connectivity, it is representing an equivalence relation and taking its join with the relation .

Fact 2 — the physicist’s potential method. Give the state a non-negative number , computable from the state, that you are allowed to spend. If operation costs real units of work and moves the balance by , call its amortised cost. Because the balance never goes below zero,

When the statement is the clean one: total real work is at most total amortised work. The balance is the proof. You do not have to trust a lemma that lives off-screen; you have to watch a line that never dips below zero.

You spend potential tokens on expensive finds and deposit them on cheap merges. For this balance sheet to prove the amortised bound, what must hold at every instant?

Two balances do the engineering work, and they fund different things.

  • Rank potential : sum the ranks over all nodes, freezing a node’s rank once it stops being a root.

  • A merge of two unequal ranks changes nothing. A merge of two equal ranks raises one root’s rank by one, so , a deposit.

  • That deposit turns an actual cost of 1 into an amortised cost of at most 2. Ranks never fall and a root of rank heads a tree of at least nodes, so the height obeys .

  • The rank balance funds the merges and caps the height. It does nothing for a find that walks a long path twice.

  • Doubling budget : charge x once each time its parent pointer changes.

  • Between two charges the subtree headed by x’s parent has at least doubled. A node stops being a direct child of a root only when its whole tree is attached beneath a tree at least as large.

  • Subtree sizes never exceed n, so no node is charged more than times, and .

  • The doubling balance funds the finds, at amortised .

#operationactualΔΦamortisedΦ
1endowment Φ₀ = 8·⌊log₂ 8⌋0+242424
2union(0,1)3+0324
3union(2,3)3+0324
4union(4,5)3+0324
5union(6,7)3+0324
6union(0,2)3+0324
7union(4,6)3+0324
8union(0,4)3+0324
9find(1)2+0224
10find(3)3-1223
11find(5)3-1222
12find(7)4-2220
13find(1) again2+0220
14find(7) again2+0220
totals37205720
Φ ≥ 0 holdsmin Φ = 0 over Φ₀ = 0 and every step.
Ledger identityΣamortised − Σactual = 20 = Φ_end − Φ_0 = 20 − 0
02040600510operationwork
Φ balancecumulative actualcumulative amortised

Doubling budget on eight elements. The endowment deposits Φ₀ = 8·⌊log₂ 8⌋ = 24 tokens; each re-hang withdraws one. Read the last row: Σ amortised − Σ actual = Φ_end.

The ledger is the doubling budget on eight elements, union by size with compression. The endowment deposits Φ₀ = 8·⌊log₂ 8⌋ = 24 tokens, each re-hang withdraws one, and the running balance never touches the axis. Read the last row rather than the first: Σ amortised − Σ actual equals Φ_end, exactly.

Neither balance alone gives the final bound. Ascending from node sizes to their levels is what composes them, because a node can be re-hung many times without its level rising, and a level that does rise climbs the iterated logarithm, which has only rungs.

NextWhat happens when union by rank meets two-pass path compression?

Two Repairs for Two Separate Demons

2 minthe simulation

Union by rank or size attacks height. Path compression attacks re-walking the same path. They are not two ways of saying “make it fast”; running one without the other leaves a different term standing.

Four policies, one workload — n = 512, 12 000 operations, 35% unions, seeded

1e31e41e51e62500500075001000012500operationscumulative nodes visited
neitherrank onlycompression onlyboth

Same workload, same order, four policies. The measured averages come out ordered exactly as the theory says — neither 79.3, rank-only 4.1, compression-only 3.3, both 3.0 nodes per operation. The mean gap between the two single repairs is small at n = 512, which is why the honest separator is the worst single operation: neither walks 101 nodes at once, compression-only walks 7, rank-only and the pair walk 5.

nlog nlog* nα(n)note
103.332
10⁹3054a billion elements
10¹⁸6054log n doubles, α does not
10⁸⁰26654atoms in the observable universe
A₄(1)2↑↑6553655α first reaches 5

Emphasised column: α(n) · highlighted row: n = 10^80

The bound is the inverse Ackermann function. Build the Ackermann hierarchy

and define . Then , and is a power tower of twos about twenty storeys high.

Every set you will ever hold has fewer than elements, so throughout. In particular , and already exceeds the number of atoms in the observable universe. Reaching needs , a number no computer can write down.

Do not confuse with the iterated logarithm. The iterated logarithm ticks once per doubling of a tower, and while . The two functions are constantly conflated; the table keeps them in separate columns for that reason.

1 minboss round

Keep the worst-case workload and scale n from 10^9 to 10^18 elements. How much more work does each operation perform?

The bound is tight, not merely an upper bound. A class of algorithms needs time (Tarjan 1979), and in the cell-probe model the lower bound holds with no restrictions (Fredman and Saks 1989).

So Union–Find is genuinely not linear. It is the slowest function you will ever actually meet.

The step from the doubling budget to is the one place this page cites instead of derives. Composing the two balances into is an intricate level argument, and the honest response to an intricate step is to attribute it and show you where the cost goes, not to wave at a proof.

NextWhere does the inverse Ackermann bound make network connectivity free?

When Connectivity Costs Nothing

2 minsystems

Kruskal’s algorithm sorts the E edges once, at cost , then asks for each edge in that order whether its two endpoints are already in one block (Kruskal 1956). The question is find and accepting the edge is merge. With both repairs the second phase costs , so it vanishes into the sort:

The same predicate answers image segmentation, where union–find is literally the inner loop of a greedy region merge (Felzenszwalb and Huttenlocher 2004), and cluster labelling, where you sweep the open sites of a lattice, merge neighbours, and ask whether two boundaries fell into one block (Hoshen and Kopelman 1976). The partition does the logic; the sort does the cost.

Next missionBinary SearchScan 10^18 records for 31.7 years, or split the sorted horizon in 60 comparisons flat.

Lineage & Attributions

  • Tarjan 1975 — Efficiency of a good but not linear set union algorithm, JACM: the upper bound for union by rank with path compression.
  • Knuth 1973 — The Art of Computer Programming, Vol. 1: the early systematic treatment of the equivalence problem whose cost Tarjan then pinned down.
  • Hopcroft and Ullman 1973 — Set merging algorithms: union by rank with the bound that precedes the inverse-Ackermann result.
  • Tarjan and van Leeuwen 1984 — Worst-case analysis of set union algorithms: the full taxonomy of link and compression policies.
  • Tarjan 1979 · Fredman and Saks 1989 — matching lower bounds, on pointer machines and in the cell-probe model respectively.
  • Birkhoff 1940 — Lattice Theory: the partition lattice, graded and semimodular.
  • Kruskal 1956 — minimum spanning trees. Felzenszwalb and Huttenlocher 2004 — graph-based image segmentation. Hoshen and Kopelman 1976 — cluster labelling.