Visualizer CodeViz · Algorithms, visualized

Part I · Union–Find · week 1

Weighted quick-union

One comparison added to union guarantees no tree is ever deeper than lg n. This is the version that makes dynamic connectivity practical.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

unionO(log n)
findO(log n)
depth≤ lg n, guaranteed
space2n

Reference: Sedgewick & Wayne, §1.5.

Weighted quick-union in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class WeightedQuickUnionUF:
    # Same forest, one extra array: sz[root] counts the sites in that tree.
    # Always hang the SMALLER tree under the larger one.

    def __init__(self, n):
        self.id = list(range(n))
        self.sz = [1] * n

    def find(self, p):
        while p != self.id[p]:
            p = self.id[p]
        return p

    def union(self, p, q):
        i, j = self.find(p), self.find(q)
        if i == j:
            return
        if self.sz[i] < self.sz[j]:       # smaller tree loses its root
            self.id[i] = j
            self.sz[j] += self.sz[i]
        else:
            self.id[j] = i
            self.sz[i] += self.sz[j]

Why it works

Why depth stays small

The depth of a site only increases when its tree is the smaller one in a union — and that means the tree it joins is at least as big, so the combined tree is at least twice the size. A site's depth can therefore increase at most lg n times, because a size can double at most lg n times before it exceeds n.

That is the whole proof, and it is worth remembering as a pattern: bound the work by counting how often a quantity can double.

Weight, not height

sz[] counts sites, not levels. Weighting by height would also work; weighting by size is what the course uses because it is easier to maintain and gives the same lg n bound. Note that sz[] is only meaningful at roots — the numbers under non-roots are stale, which is fine because nothing reads them.

The numbers that matter

For 109 sites and 109 unions: quick-find needs about 30 years, weighted quick-union about 6 seconds. Same problem, same machine — the algorithm is the difference. This is the course's headline example of design beating hardware.

Watch for

  • The tie case (sz[i] == sz[j]) takes the else branch, so j hangs under i.
  • The number under each root in the picture is its sz. Sum of all root sizes = n, always.
  • Try the path preset that ruined quick-union: the forest now stays flat.

What to try in the animation

n sites, then a list of p-q pairs to connect. The default is tinyUF.txt from the course.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Weighted quick-union in the player →

The rest of Union–Find