Union-find deeper: union by size and path halving

Why this matters

A union-find structure answers one question quickly: are these two items in the same group, and if not, join their groups. Social apps use it to find friend circles. Image editors use it to find blobs of connected pixels. Kruskal's method for a cheapest network of roads uses it to avoid building a loop. The lesson called Union-find and MST, earlier in this module, builds the basic structure and uses it for a minimum spanning tree. This lesson is about speed.

The basic structure can become slow. A single question can take thousands of steps on a list of only a few thousand items. This lesson shows exactly how that happens, why two small changes fix it, what each change buys, and what the fixed version costs. The proof here covers one half of the claim completely. The other half is a known result that we state but do not prove, and the lesson says which is which.

The basic structure, briefly

Each item is a number from 0 to n minus 1. An array called parent holds one value per item. At the start, every item is its own parent, so every item is a group on its own.

A root is an item whose parent is itself. Two items are in the same group when following parent links from each of them reaches the same root.

There are two operations.

• find(x) follows parent links from x until it reaches a root, and returns that root. Each link it follows is one step.
• unite(a, b) finds the root of a and the root of b. If they are the same, the two items are already in one group, and nothing changes. If they are different, it makes one root the parent of the other. That joins the two groups into one.

The depth of an item is the number of steps from it up to its root. An item whose parent is the root has depth 1. The root itself has depth 0. A call to find on an item costs about as many steps as that item's depth.

A chain that breaks the basic version

Start with the simplest bad case. Take 10000 items, numbered 0 to 9999, and run these unions in order:

unite(1, 0)
unite(2, 1)
unite(3, 2)
...
unite(9999, 9998)

Each union joins a brand new item to the group that already holds all the earlier items. The basic version links the root of the second item under the root of the first item. Here the first item is always the new one, which is a singleton with itself as root. So each new item becomes the root, and the old root sinks one level down.

After the last union, item 0 is 9999 links below the top. Every find(0) walks all 9999 links. A program that asks about item 0 a thousand more times does about ten million steps just for that.

The basic version has no rule that looks at how big each group is. It does not care that a group of 9000 items is being pushed under a group of one item. That is the whole problem, and the next section fixes it.

Problem 1: linking the wrong way round

The fix is called union by size. Each root stores the number of items in its group. When two groups join, the root of the smaller group goes under the root of the larger group. If the sizes are equal, either root can go under the other.

Here is a small example with 6 items. The program below runs five unions and prints the parent and size arrays after each step. The arrays are the same class used in the experiment later, with the printing added. It uses union by size and no halving, which is the next idea.

The output shows the state after each step. Read the parent line for who points to whom, and the size line for the number stored at each root. A non-root keeps the size it had when it stopped being a root. Nothing reads those numbers.

Worked example: 6 nodes, union by size, no halving
start (every node is its own set)
  parent: 0 1 2 3 4 5
  size:   1 1 1 1 1 1
after unite(0, 1)
  parent: 0 0 2 3 4 5
  size:   2 1 1 1 1 1
after unite(2, 3)
  parent: 0 0 2 2 4 5
  size:   2 1 2 1 1 1
after unite(1, 3)
  parent: 0 0 0 2 4 5
  size:   4 1 2 1 1 1
find(2) = 0, find(0) = 0
after unite(4, 5) and unite(0, 4)
  parent: 0 0 0 2 0 4
  size:   6 1 2 1 2 1

Walk through the third union by hand. unite(1, 3) first finds the root of 1, which is 0, and the root of 3, which is 2. Both groups have size 2. The sizes are equal, so 2 goes under 0. The root 0 now has size 4. Item 3 is now two links from the root: 3 points to 2, and 2 points to 0. That is the only way depth grows in this run, and the next section shows that it always means the group has at least doubled.

The last union, unite(0, 4), joins a group of size 4 (root 0) with a group of size 2 (root 4). The smaller group goes under the larger one, so 4 goes under 0. Item 5 is now two links from the root, which is still a short path.

Now compare with the chain from before. Under union by size, the same 10000-item chain of unions gives a tree of depth 1 for item 0. Experiment 1 below shows the number.

Proof: depth never goes above log2 n

The claim is simple to state. With union by size, every item has depth at most log2 n, where n is the number of items. Here log2 n means "the power of 2 that gives n". For n equal to 200000, log2 n is about 17.6, so depth is at most 17. For n equal to 1000000, log2 n is about 19.9, so depth is at most 19.

The proof works on one idea. An item's depth goes up only at one moment: when the root of its group is placed under another root in a union. Union by size places the smaller group under the larger group. So the group whose root moves has size at most the size of the group it joins.

After the move, every item in the moved group is one level deeper, and every item in the moved group now belongs to a group of size at least twice the old size. The size of the moved group was s. The new group has size at least s plus s, which is 2s.

So each time an item's depth goes up by one, the size of its group at least doubles. Now argue by induction on the depth d.

• An item at depth 0 is a root. Its group has size at least 1, which is 2 to the power 0.
• Suppose every item at depth d is in a group of size at least 2 to the power d. An item whose depth becomes d plus 1 was moved along with its group. Just before the move, its group had size at least 2 to the power d. The move doubles the group, so its size is now at least 2 to the power d plus 1.

Group sizes never shrink, and no group can have more than n items. So if an item is at depth d, then 2 to the power d is at most n. Taking log2 of both sides gives d at most log2 n. That is the claim.

A worked check. In the 6-item example, item 5 has depth 2. The bound says its group must have at least 2 to the power 2, which is 4, items. Its group has 6 items, so the bound holds.

What the bound buys is this. A find costs at most log2 n steps, even in the worst case. With one million items, that is at most 19 steps. The bound is about the worst case, not the average, so it protects against the chain.

Measuring it: the experiment

The next program runs four versions of the structure on three kinds of input. It counts steps instead of measuring time, so the numbers are the same on every run. A step is one pass around the while loop in find. The random inputs use a fixed seed, so the program makes the same unions and the same finds each time.

The four versions come from two switches. The first switch, bySize, turns union by size on or off. The second, halving, turns path halving on or off. Path halving is explained in the next section, so for now read the halving switch as "off" in the first part of the output.

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <utility>
#include <vector>
 
class DisjointSet {
public:
    // bySize: join the smaller set under the larger one.
    // halving: make find() skip every other step on the way up.
    DisjointSet(int n, bool bySize, bool halving)
        : parent_(n), size_(n, 1), bySize_(bySize), halving_(halving) {
        std::iota(parent_.begin(), parent_.end(), 0);
    }
 
    int find(int x) {
        while (parent_[x] != x) {
            ++steps_;
            if (halving_) {
                parent_[x] = parent_[parent_[x]];
            }
            x = parent_[x];
        }
        return x;
    }
 
    bool unite(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return false;
        if (bySize_) {
            if (size_[ra] < size_[rb]) std::swap(ra, rb);
            size_[ra] += size_[rb];
        }
        parent_[rb] = ra;
        return true;
    }
 
    int depth(int x) const {
        int d = 0;
        while (parent_[x] != x) {
            x = parent_[x];
            ++d;
        }
        return d;
    }
 
    int maxDepth() const {
        int best = 0;
        for (int x = 0; x < static_cast<int>(parent_.size()); ++x) {
            best = std::max(best, depth(x));
        }
        return best;
    }
 
    long long steps() const { return steps_; }
 
    void print(const std::string& label) const {
        std::cout << label << "\n  parent:";
        for (int p : parent_) std::cout << ' ' << p;
        std::cout << "\n  size:  ";
        for (int s : size_) std::cout << ' ' << s;
        std::cout << "\n";
    }
 
private:
    std::vector<int> parent_;
    std::vector<int> size_;
    bool bySize_;
    bool halving_;
    long long steps_ = 0;
};
 
int pick(std::mt19937& gen, int n) {
    return static_cast<int>(gen() % static_cast<std::uint32_t>(n));
}
 
void chainTest(const std::string& name, bool bySize, bool halving, int n) {
    DisjointSet ds(n, bySize, halving);
    for (int i = 1; i < n; ++i) ds.unite(i, i - 1);
    int depthBefore = ds.depth(0);
 
    long long before = ds.steps();
    ds.find(0);
    long long firstFind = ds.steps() - before;
 
    before = ds.steps();
    for (int i = 0; i < 1000; ++i) ds.find(0);
    long long next1000 = ds.steps() - before;
 
    std::cout << name << ": depth of node 0 = " << depthBefore
              << ", steps for first find = " << firstFind
              << ", steps for next 1000 finds = " << next1000 << '\n';
}
 
void randomTest(const std::string& name, bool bySize, bool halving, int n, int unions, int finds) {
    DisjointSet ds(n, bySize, halving);
    std::mt19937 gen(2026);
    for (int i = 0; i < unions; ++i) {
        int a = pick(gen, n);
        int b = pick(gen, n);
        ds.unite(a, b);
    }
    long long afterUnions = ds.steps();
    for (int i = 0; i < finds; ++i) ds.find(pick(gen, n));
    long long findSteps = ds.steps() - afterUnions;
 
    std::cout << name << ": max depth = " << ds.maxDepth()
              << ", total steps in " << finds << " finds = " << findSteps << '\n';
}
 
void binomialTest(const std::string& name, bool halving, int levels) {
    int n = 1 << levels;
    DisjointSet ds(n, true, halving);
    for (int k = 0; k < levels; ++k) {
        for (int i = 0; i < n; i += 1 << (k + 1)) {
            ds.unite(i, i + (1 << k));
        }
    }
    int deepest = 0;
    int deepestDepth = 0;
    for (int x = 0; x < n; ++x) {
        int d = ds.depth(x);
        if (d > deepestDepth) {
            deepestDepth = d;
            deepest = x;
        }
    }
    long long before = ds.steps();
    for (int i = 0; i < 1000; ++i) ds.find(deepest);
    long long steps1000 = ds.steps() - before;
 
    std::cout << name << ": n = " << n << ", deepest node " << deepest
              << " at depth " << deepestDepth
              << ", steps for 1000 finds of it = " << steps1000 << '\n';
}
 
void traceDemo() {
    DisjointSet ds(6, true, false);
    ds.print("start (every node is its own set)");
    ds.unite(0, 1);
    ds.print("after unite(0, 1)");
    ds.unite(2, 3);
    ds.print("after unite(2, 3)");
    ds.unite(1, 3);
    ds.print("after unite(1, 3)");
    std::cout << "find(2) = " << ds.find(2) << ", find(0) = " << ds.find(0) << "\n";
    ds.unite(4, 5);
    ds.unite(0, 4);
    ds.print("after unite(4, 5) and unite(0, 4)");
}
 
int main() {
    std::cout << "Worked example: 6 nodes, union by size, no halving\n";
    traceDemo();
 
    std::cout << "\nExperiment 1: chain of 10000 unions, unite(i, i-1)\n";
    chainTest("arbitrary link, no shortcut", false, false, 10000);
    chainTest("arbitrary link, halving    ", false, true, 10000);
    chainTest("by size, no shortcut        ", true, false, 10000);
    chainTest("by size, halving           ", true, true, 10000);
 
    std::cout << "\nExperiment 2: 200000 random unions, then 1000000 random finds, n = 200000\n";
    randomTest("arbitrary link, no shortcut", false, false, 200000, 200000, 1000000);
    randomTest("arbitrary link, halving    ", false, true, 200000, 200000, 1000000);
    randomTest("by size, no shortcut        ", true, false, 200000, 200000, 1000000);
    randomTest("by size, halving           ", true, true, 200000, 200000, 1000000);
 
    std::cout << "\nExperiment 3: binomial tree built with union by size, 2^17 nodes\n";
    binomialTest("by size, no shortcut", false, 17);
    binomialTest("by size, halving   ", true, 17);
    return 0;
}

Compile and run it with:

g++ -std=c++20 -Wall -o dsu_bench dsu_bench.cpp
./dsu_bench

The run takes a minute or two, because the first row of Experiment 2 does about 11 billion steps. On the machine used to check this lesson it took 105 seconds.

The output is:

Worked example: 6 nodes, union by size, no halving
start (every node is its own set)
  parent: 0 1 2 3 4 5
  size:   1 1 1 1 1 1
after unite(0, 1)
  parent: 0 0 2 3 4 5
  size:   2 1 1 1 1 1
after unite(2, 3)
  parent: 0 0 2 2 4 5
  size:   2 1 2 1 1 1
after unite(1, 3)
  parent: 0 0 0 2 4 5
  size:   4 1 2 1 1 1
find(2) = 0, find(0) = 0
after unite(4, 5) and unite(0, 4)
  parent: 0 0 0 2 0 4
  size:   6 1 2 1 2 1
 
Experiment 1: chain of 10000 unions, unite(i, i-1)
arbitrary link, no shortcut: depth of node 0 = 9999, steps for first find = 9999, steps for next 1000 finds = 9999000
arbitrary link, halving    : depth of node 0 = 9999, steps for first find = 5000, steps for next 1000 finds = 5992
by size, no shortcut        : depth of node 0 = 1, steps for first find = 1, steps for next 1000 finds = 1000
by size, halving           : depth of node 0 = 1, steps for first find = 1, steps for next 1000 finds = 1000
 
Experiment 2: 200000 random unions, then 1000000 random finds, n = 200000
arbitrary link, no shortcut: max depth = 20454, total steps in 1000000 finds = 11087587505
arbitrary link, halving    : max depth = 3, total steps in 1000000 finds = 890421
by size, no shortcut        : max depth = 8, total steps in 1000000 finds = 1822493
by size, halving           : max depth = 2, total steps in 1000000 finds = 842349
 
Experiment 3: binomial tree built with union by size, 2^17 nodes
by size, no shortcut: n = 131072, deepest node 131071 at depth 17, steps for 1000 finds of it = 17000
by size, halving   : n = 131072, deepest node 131071 at depth 17, steps for 1000 finds of it = 1015

Experiment 2 checks the bound from the proof. The largest depth under union by size and no halving is 8, and log2 200000 is about 17.6, so 8 is inside the bound. Experiment 3 hits the bound exactly. A binomial tree here is built in levels, where each level joins pairs of trees from the level below. Its tree has 2 to the power 17 items, and the deepest item sits 17 links below its root.

Problem 2: repeated finds keep paying

Union by size keeps every tree shallow. It does not stop a single item from being deep. Look at the third block of Experiment 3. The deepest item sits at depth 17. Under union by size with no halving, each of 1000 finds on that item costs 17 steps, so the total is 17000. The same work is repeated over and over, and the program never remembers what it learned on the last walk.

Path halving fixes the repetition. During a find, each item on the way up is pointed at its grandparent instead of its parent. The walk then skips every other item. The code change is one line:

parent_[x] = parent_[parent_[x]];
x = parent_[x];

Take a 5-item chain where parent is [1, 2, 3, 4, 4], so item 0 is four links below the root 4. Run find(0) with halving:

• At x equal to 0, the parent of 0 becomes the parent of 1, which is 2. The walk moves to 2.
• At x equal to 2, the parent of 2 becomes the parent of 3, which is 4. The walk moves to 4.
• At x equal to 4, the item is a root, so the walk stops.

Two steps instead of four. The parent array is now [2, 2, 4, 4, 4]. Item 0 is two links from the root instead of four. The next find(0) is shorter again.

Halving does not change which root an item reaches. Each new parent is a grandparent, which is still an ancestor in the same group. Halving also never raises an item's depth, so the proof from the previous section still holds with halving turned on.

Experiment 3 shows the effect. With union by size and no halving, the 1000 finds cost 17000 steps. With halving, they cost 1015 steps. The first few finds do the work, and the later ones cost about one step each. An item always takes at least one step, because it is never the root, so 1000 finds need at least 1000 steps. The extra 15 steps are the cost of the first walk.

Why both tricks are needed

Each trick covers a weakness the other one leaves open. Experiment 2 shows this best. It has four rows, and each row turns the two switches on or off.

Read the first row first. Without union by size, the random unions build a tree 20454 links tall, even though only 200000 items exist. The first find on such an item is slow, and one million finds cost 11 billion steps.

Halving alone, the second row, fixes most of that. Its maximum depth falls to 3 and its total is 890421. On random input, halving does a lot of the work by itself. But the chain experiment shows what it cannot do. In Experiment 1, the arbitrary link with halving still costs 5000 steps on the first find(0) in a chain of 10000 items. Halving only shortens the path during a walk. It does not stop the first walk from being long. Union by size is what stops a single walk from being long, and the proof in the previous section is the guarantee.

Union by size alone, the third row, has the guarantee but keeps paying for repeated finds on a deep item. Experiment 3 shows 17000 steps where halving costs 1015.

So the two tricks split the work. Union by size bounds the worst single walk to log2 n steps. Halving makes the repeated walks cheap and keeps the trees flat over time. The fourth row, with both on, has the lowest maximum depth and the lowest total steps in the table.

How close to constant is it

The structure with both tricks is the one that most libraries use. The known result is that the average cost per operation, over any long sequence of unions and finds, is bounded by a function called the inverse Ackermann function, written α(n). Robert Tarjan published the analysis in 1975, and later work by Tarjan and van Leeuwen refined it.

The inverse Ackermann function is so slow to grow that α(n) is at most 4 for any n that fits in computer memory. An average of 4 steps per operation is what "near constant" means here. The proof is longer than the one in this lesson, and this lesson does not reproduce it. The claim to remember is: union by size gives a proof of log2 n per walk, and both tricks together give the much smaller bound.

The random experiment is a rough check of that claim. Its fourth row costs 842349 steps for one million finds, which is about 0.84 steps per find. That number is a measurement on one input, not a proof. Other inputs can cost more per operation, and this run does not show the worst case.

Common mistakes

Skipping the same-root check. If two items are already in one group, unite must do nothing. Without the check if (ra == rb) return false;, the code would run size_[ra] += size_[rb] with the same root on both sides. The size of the group doubles, and nothing else changes. Here is a small test that shows the effect. It sets up a group of size 1 and unites it with itself. The size should stay at 1:

set size after uniting a set with itself: 2

Every later decision that uses sizes is then wrong, so the bound from the proof no longer holds for that structure.

Comparing sizes before finding the roots. The code must compare size_[ra] and size_[rb], the sizes of the two roots. Comparing size_[a] and size_[b] looks similar, but a and b are often not roots. Their stored sizes are stale, so the smaller group may go on top. If the code then links the items themselves instead of their roots, it can cut a group in two. Always call find first.

Using an item number that is out of range. Item numbers run from 0 to n minus 1. A number equal to n is outside the array. C++ does not check this by default, so the program may read garbage memory. Compile with the library's assertion switch to get a check and a clear message:

g++ -std=c++20 -Wall -D_GLIBCXX_ASSERTIONS -o mistake_bounds mistake_bounds.cpp

Running a program with parent[6] on a six-item array gives this message and then the program stops with exit code 134:

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The useful part is Assertion '__n < this->size()' failed. It means an index was too large for the array.

Calling unite with one argument. The class needs two item numbers. A call with one number is a compile error, and the compiler lists the signature it expected. A small program with a unite that takes two numbers, called with one, prints these lines:

mistake_args.cpp: In function ‘int main()’:
mistake_args.cpp:9:26: error: no matching function for call to ‘Pair::unite(int)’
    9 |     std::cout << ds.unite(1) << '\n';
      |                  ~~~~~~~~^~~
mistake_args.cpp:9:26: note: there is 1 candidate
mistake_args.cpp:4:10: note: candidate 1: ‘bool Pair::unite(int, int)’
    4 |     bool unite(int a, int b) { return a != b; }
      |          ^~~~~
mistake_args.cpp:4:10: note: candidate expects 2 arguments, 1 provided

Read the note: candidate expects 2 arguments, 1 provided line first. It names the missing argument.

Forgetting that the bound is per item. The log2 n bound applies to the depth of each item. It does not say that the whole structure is shallow. A tree with a few deep items and many shallow ones still satisfies the bound, and a find on one of the deep items still costs as much as the depth.

Practice

Exercise 1

Start with 4 items, 0 to 3. Run unite(1, 0), then unite(2, 1), then unite(3, 2). Write the parent array for the basic version, which links the root of the second item under the root of the first. Then write the parent array for union by size. Use the rule from this lesson: the smaller group goes under the larger one, and on a tie the root of the second item goes under the root of the first.

Show the answer

Basic version: [1, 2, 3, 3]. Each new item becomes the root, and the old root sinks one level.

Union by size: [1, 1, 1, 1]. Item 1 is the root from the first union, and each later singleton or small group goes under it. Every item has depth 1 or less.

Exercise 2

Under union by size, can an item have depth 4 in a set of 10 items? Explain your answer using the proof.

Show the answer

No. Depth 4 needs a group of at least 2 to the power 4, which is 16, items. A set of 10 items cannot hold 16 items, so depth 4 is impossible. The bound allows depth 3 at most.

Exercise 3

The parent array is [1, 2, 3, 4, 4]. Run find(0) with path halving. Write the parent array after the call, and say how many steps the call took and what it returned.

Show the answer

The array becomes [2, 2, 4, 4, 4]. The call takes 2 steps, as shown in the worked example. It returns 4, the root.

Exercise 4

A union-find structure has 1000000 items and uses union by size. What is the largest depth any item can have? Show how you got the number.

Show the answer

The answer is 19. The bound says depth is at most log2 of 1000000, which is about 19.9, so at most 19. Depth 20 would need 2 to the power 20, which is 1048576 items, and that is more than 1000000. Depth 19 needs 2 to the power 19, which is 524288 items, and that fits. The bound says nothing deeper is possible. A tree of depth 19 can be built with 2 to the power 19 items, so 19 is the largest possible.

Exercise 5

In Experiment 3, the halving version costs 1015 steps for 1000 finds of the deepest item. Explain why the total is at least 1000, and where the other 15 steps come from.

Show the answer

Each find on an item that is not a root takes at least one step, because the loop runs at least once. So 1000 finds take at least 1000 steps. The extra 15 steps come from the first few finds, which walk the long path before halving has shortened it.

Summary

• The basic structure can build a chain of depth n, and then one find costs n steps.
• Union by size puts the smaller group under the larger one, and that caps every item's depth at log2 n.
• Path halving points each item on a walk at its grandparent, which makes repeated finds cheap.
• Union by size gives the guarantee on a single walk, and halving makes the later walks cheap. Each trick covers what the other misses.
• The proof of log2 n is in this lesson. The inverse Ackermann bound for both tricks together is a known result that is stated, not proved, here.
• Run a counter of steps, not a timer, to compare versions. Timing depends on the machine, and step counts do not.