wire / wire-format / union-find

Union-Find (Disjoint Set Union)

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).

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Union-Find (Disjoint Set Union)

wire format

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).

fieldsizemeaning
Parent arrayn elementsparent[i] = parent of element i. Root has parent[i] = i (or -1).
Rank/size arrayn elementsrank[i] = height of tree rooted at i (or size of set). Used for union by rank/size.
Find (with path compression)O(α(n)) amortizedRecursively find root. Path compression: set parent of each visited node to root.
Union (by rank)O(α(n)) amortizedFind roots of x and y. If different, attach shorter tree to taller tree. If equal rank, increment rank.
Union (by size)O(α(n)) amortizedAttach 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)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/union-find or /wire-format/union-find.json