wire / wire-format / union-find
Union-Find (DSU) manages a partition of elements into disjoint sets. Operations: find(x) returns the representative of x's set, union(x,y) merges the sets of x and y. Optimizations: path compression (flatten tree during find), union by rank/size (attach smaller tree to larger). Amortized O(α(n)) per operation (α = inverse Ackermann, effectively constant).
aka: Union-Find (Disjoint Set Union)
spec: Union-Find (DSU)
Union-Find (DSU) manages a partition of elements into disjoint sets. Operations: find(x) returns the representative of x's set, union(x,y) merges the sets of x and y. Optimizations: path compression (flatten tree during find), union by rank/size (attach smaller tree to larger). Amortized O(α(n)) per operation (α = inverse Ackermann, effectively constant).
| field | size | meaning |
|---|---|---|
| Parent array | n elements | parent[i] = parent of element i. Root has parent[i] = i (or -1). |
| Rank/size array | n elements | rank[i] = height of tree rooted at i (or size of set). Used for union by rank/size. |
| Find (with path compression) | O(α(n)) amortized | Recursively find root. Path compression: set parent of each visited node to root. |
| Union (by rank) | O(α(n)) amortized | Find roots of x and y. If different, attach shorter tree to taller tree. If equal rank, increment rank. |
| Union (by size) | O(α(n)) amortized | Attach smaller set to larger set. Update size of larger set. |
| Inverse Ackermann α(n) | function | α(n) ≤ 4 for all practical n (n ≤ 2^2^2^2^2^2^2...). Effectively constant. |
example:
00 00 00 00
Union-Find (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/union-find
or /wire-format/union-find.json