Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 20 Prof. Erik Demaine Introduction to Algorithms Day 33 L20.2? 2001 by Erik D. Demaine Disjoint-set data structure (Union-Find) Problem: Maintain a dynamic collection of pairwise-disjoint sets S = {S 1 , S 2 , …, S r }. Each set S i has one element distinguished as the representative element, rep[S i ]. Must support 3 operations: ? MAKE-SET(x): adds new set {x} to S with rep[{x}] = x (for any x ? S i for all i). ? UNION(x, y): replaces sets S x , S y with S x ∪ S y in S for any x, y in distinct sets S x , S y . ? FIND-SET(x): returns representative rep[S x ] of set S x containing element x. Introduction to Algorithms Day 33 L20.3? 2001 by Erik D. Demaine Simple linked-list solution Store each set S i = {x 1 , x 2 , …, x k } as an (unordered) doubly linked list. Define representative element rep[S i ] to be the front of the list, x 1 . … S i : x 1 x 2 x k rep[S i ] ? MAKE-SET(x) initializes x as a lone node. ? FIND-SET(x) walks left in the list containing x until it reaches the front of the list. ? UNION(x, y) concatenates the lists containing x and y, leaving rep. as FIND-SET[x]. – Θ(1) – Θ(n) – Θ(n) Introduction to Algorithms Day 33 L20.4? 2001 by Erik D. Demaine Simple balanced-tree solution Store each set S i = {x 1 , x 2 , …, x k } as a balanced tree (ignoring keys). Define representative element rep[S i ] to be the root of the tree. x 1 x 4 x 3 x 2 x 5 ? MAKE-SET(x) initializes x as a lone node. ? FIND-SET(x) walks up the tree containing x until it reaches the root. ? UNION(x, y) concatenates the trees containing x and y, changing rep. S i ={x 1 , x 2 , x 3 , x 4 , x 5 } rep[S i ] – Θ(1) – Θ(lg n) – Θ(lg n) Introduction to Algorithms Day 33 L20.5? 2001 by Erik D. Demaine Plan of attack We will build a simple disjoint-union data structure that, in an amortized sense, performs significantly better than Θ(lg n) per op., even better than Θ(lg lg n), Θ(lg lg lg n), etc., but not quite Θ(1). To reach this goal, we will introduce two key tricks. Each trick converts a trivial Θ(n) solution into a simple Θ(lg n) amortized solution. Together, the two tricks yield a much better solution. First trick arises in an augmented linked list. Second trick arises in a tree structure. Introduction to Algorithms Day 33 L20.6? 2001 by Erik D. Demaine Augmented linked-list solution … S i : x 1 x 2 x k rep[S i ] rep Store set S i = {x 1 , x 2 , …, x k } as unordered doubly linked list. Define rep[S i ] to be front of list, x 1 . Each element x j also stores pointer rep[x j ] to rep[S i ]. ? FIND-SET(x) returns rep[x]. ? UNION(x, y) concatenates the lists containing x and y, and updates the rep pointers for all elements in the list containing y. – Θ(n) – Θ(1) Introduction to Algorithms Day 33 L20.7? 2001 by Erik D. Demaine Example of augmented linked-list solution S x : x 1 x 2 rep[S x ] rep Each element x j stores pointer rep[x j ] to rep[S i ]. UNION(x, y) ? concatenates the lists containing x and y, and ? updates the rep pointers for all elements in the list containing y. S y : y 1 y 2 y 3 rep[S y ] rep Introduction to Algorithms Day 33 L20.8? 2001 by Erik D. Demaine Example of augmented linked-list solution S x ∪ S y : x 1 x 2 rep[S x ] rep Each element x j stores pointer rep[x j ] to rep[S i ]. UNION(x, y) ? concatenates the lists containing x and y, and ? updates the rep pointers for all elements in the list containing y. y 1 y 2 y 3 rep[S y ] rep Introduction to Algorithms Day 33 L20.9? 2001 by Erik D. Demaine Example of augmented linked-list solution S x ∪ S y : x 1 x 2 rep[S x ∪S y ] Each element x j stores pointer rep[x j ] to rep[S i ]. UNION(x, y) ? concatenates the lists containing x and y, and ? updates the rep pointers for all elements in the list containing y. y 1 y 2 y 3 rep Introduction to Algorithms Day 33 L20.10? 2001 by Erik D. Demaine Alternative concatenation S x : x 1 x 2 rep[S y ] UNION(x, y) could instead ? concatenate the lists containing y and x, and ? update the rep pointers for all elements in the list containing x. y 1 y 2 y 3 rep rep[S x ] rep S y : Introduction to Algorithms Day 33 L20.11? 2001 by Erik D. Demaine Alternative concatenation S x ∪ S y : x 1 x 2 rep[S y ] UNION(x, y) could instead ? concatenate the lists containing y and x, and ? update the rep pointers for all elements in the list containing x. y 1 y 2 y 3 rep[S x ] rep rep Introduction to Algorithms Day 33 L20.12? 2001 by Erik D. Demaine Alternative concatenation S x ∪ S y : x 1 x 2 UNION(x, y) could instead ? concatenate the lists containing y and x, and ? update the rep pointers for all elements in the list containing x. y 1 y 2 y 3 rep rep rep[S x ∪S y ] Introduction to Algorithms Day 33 L20.13? 2001 by Erik D. Demaine Trick 1: Smaller into larger To save work, concatenate smaller list onto the end of the larger list. Cost = Θ(length of smaller list). Augment list to store its weight (# elements). Let n denote the overall number of elements (equivalently, the number of MAKE-SET operations). Let m denote the total number of operations. Let f denote the number of FIND-SET operations. Theorem: Cost of all UNION’s is O(n lg n). Corollary: Total cost is O(m + n lg n). Introduction to Algorithms Day 33 L20.14? 2001 by Erik D. Demaine Analysis of Trick 1 To save work, concatenate smaller list onto the end of the larger list. Cost = Θ(1 + length of smaller list). Theorem: Total cost of UNION’s is O(n lg n). Proof. Monitor an element x and set S x containing it. After initial MAKE-SET(x), weight[S x ] = 1. Each time S x is united with set S y , weight[S y ] ≥ weight[S x ], pay 1 to update rep[x], and weight[S x ] at least doubles (increasing by weight[S y ]). Each time S y is united with smaller set S y , pay nothing, and weight[S x ] only increases. Thus pay ≤ lg n for x. Introduction to Algorithms Day 33 L20.15? 2001 by Erik D. Demaine Representing sets as trees Store each set S i = {x 1 , x 2 , …, x k } as an unordered, potentially unbalanced, not necessarily binary tree, storing only parent pointers. rep[S i ] is the tree root. x 1 x 4 x 3 x 2 x 5 S i ={x 1 , x 2 , x 3 , x 4 , x 5 , x 6 } rep[S i ] ? MAKE-SET(x) initializes x as a lone node. ? FIND-SET(x) walks up the tree containing x until it reaches the root. ? UNION(x, y) concatenates the trees containing x and y… – Θ(1) – Θ(depth[x]) x 6 Introduction to Algorithms Day 33 L20.16? 2001 by Erik D. Demaine Trick 1 adapted to trees UNION(x, y) can use a simple concatenation strategy: Make root FIND-SET(y) a child of root FIND-SET(x). ? FIND-SET(y) = FIND-SET(x). y 1 y 4 y 3 y 2 y 5 We can adapt Trick 1 to this context also: Merge tree with smaller weight into tree with larger weight. Height of tree increases only when its size doubles, so height is logarithmic in weight. Thus total cost is O(m + f lg n). x 1 x 4 x 3 x 2 x 5 x 6 Introduction to Algorithms Day 33 L20.17? 2001 by Erik D. Demaine Trick 2: Path compression When we execute a FIND-SET operation and walk up a path p to the root, we know the representative for all the nodes on path p. y 1 y 4 y 3 y 2 y 5 x 1 x 4 x 3 x 2 x 5 x 6 Path compression makes all of those nodes direct children of the root. Cost of FIND-SET(x) is still Θ(depth[x]). FIND-SET(y 2 ) Introduction to Algorithms Day 33 L20.18? 2001 by Erik D. Demaine Trick 2: Path compression When we execute a FIND-SET operation and walk up a path p to the root, we know the representative for all the nodes on path p. y 1 y 4 y 3 y 2 y 5 x 1 x 4 x 3 x 2 x 5 x 6 Path compression makes all of those nodes direct children of the root. Cost of FIND-SET(x) is still Θ(depth[x]). FIND-SET(y 2 ) Introduction to Algorithms Day 33 L20.19? 2001 by Erik D. Demaine Trick 2: Path compression When we execute a FIND-SET operation and walk up a path p to the root, we know the representative for all the nodes on path p. y 1 y 4 y 3 y 2 y 5 x 1 x 4 x 3 x 2 x 5 x 6 FIND-SET(y 2 ) Path compression makes all of those nodes direct children of the root. Cost of FIND-SET(x) is still Θ(depth[x]). Introduction to Algorithms Day 33 L20.20? 2001 by Erik D. Demaine Analysis of Trick 2 alone Theorem: Total cost of FIND-SET’s is O(m lg n). Proof: Amortization by potential function. The weight of a node x is # nodes in its subtree. Define φ(x 1 , …, x n ) = Σ i lg weight[x i ]. UNION(x i , x j ) increases potential of root FIND-SET(x i ) by at most lg weight[root FIND-SET(x j )] ≤ lg n. Each step down p → c made by FIND-SET(x i ), except the first, moves c’s subtree out of p’s subtree. Thus if weight[c] ≥ ? weight[p], φ decreases by ≥ 1, paying for the step down. There can be at most lg n steps p → c for which weight[c] < ? weight[p]. Introduction to Algorithms Day 33 L20.21? 2001 by Erik D. Demaine Analysis of Trick 2 alone Theorem: If all UNION operations occur before all FIND-SET operations, then total cost is O(m). Proof: If a FIND-SET operation traverses a path with k nodes, costing O(k) time, then k –2nodes are made new children of the root. This change can happen only once for each of the n elements, so the total cost of FIND-SET is O(f + n). Introduction to Algorithms Day 33 L20.22? 2001 by Erik D. Demaine Ackermann’s function A Define ? ? ? ≥ = + = + ? .1 if ,0 if )( 1 )( )1( 1 k k jA j jA j k k Define α(n) = min {k : A k (1) ≥ n} ≤ 4 for practical n. A 0 (j) = j + 1 A 1 (j) ~ 2 j A 2 (j) ~ 2j 2 j > 2 j A 3 (j) > A 4 (j) is a lot bigger. 2 2 2 2 j . . . j A 0 (1) = 2 A 1 (1) = 3 A 2 (1) = 7 A 3 (1) = 2047 A 4 (1) > – iterate j+1 times 2 2 2 2 2047 . . . 2048 Introduction to Algorithms Day 33 L20.23? 2001 by Erik D. Demaine Analysis of Tricks 1 + 2 Theorem: In general, total cost is O(m α(n)). (long, tricky proof – see Section 21.4 of CLRS) Introduction to Algorithms Day 33 L20.24? 2001 by Erik D. Demaine Application: Dynamic connectivity Suppose a graph is given to us incrementally by ? ADD-VERTEX(v) ? ADD-EDGE(u, v) and we want to support connectivity queries: ? CONNECTED(u, v): Are u and v in the same connected component? For example, we want to maintain a spanning forest, so we check whether each new edge connects a previously disconnected pair of vertices. Introduction to Algorithms Day 33 L20.25? 2001 by Erik D. Demaine Application: Dynamic connectivity Sets of vertices represent connected components. Suppose a graph is given to us incrementally by ? ADD-VERTEX(v) –MAKE-SET(v) ? ADD-EDGE(u, v) – if not CONNECTED(u, v) then UNION(v, w) and we want to support connectivity queries: ? CONNECTED(u, v): – FIND-SET(u) = FIND-SET(v) Are u and v in the same connected component? For example, we want to maintain a spanning forest, so we check whether each new edge connects a previously disconnected pair of vertices.