Union-Find and Amortization

Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Erik Demaine, Srini Devadas and Nancy Lynch February 20, 2015 6.046J/18.410J Recitation 3 Union-Find and Amortization 1 Introduction A union-find data structure, also known as a disjoint-set data structure, is a data structure that can keep track of a collection of pairwise disjoint sets S = {S1 , S2 , . . . , Sr } containing a total of n elements. Each set Si has a single, arbitrarily chosen element that can serve as a representative for the entire set, denoted as rep[Si ]. Specifically, we wish to support the following operations: • M AKE -S ET(x), which adds a new set {x} to S with rep[{x}] = x. • F IND -S ET(x), which determines which set Sx ∈ S contains x and returns rep[Sx ]. • U NION(x, y), which replaces Sx and Sy with Sx ∪ Sy in S for any x, y in distinct sets Sx , Sy . Furthermore, we want to make these as efficient as possible. We will go through the process of creating a data structure that, in an amortized sense, performs spectacularly. 1.1 Motivation Union-find data structure is used in many different algorithms. A natural use case of union find is keeping track of connected component in an undirected graph where nodes and edges could be added dynamically. We start with the initial connected components as Si ’s. As we add a node v along with its edges E = {(v, vj )}, we either 1. Call M AKE -S ET if E = ∅ to make a new component. 2. Call F IND -S ET(vj ) to find the component node v will be connected to, and call U NION to connect all those components connected through v. Another use case of this data structure is in Kruskal’s algorithm which you will see in future lectures. 2 Recitation 3: Union-Find and Amortization Figure 1: A simple doubly linked list. 2 Starting Out 2.1 Linked List Solution A naı̈ve way to solve this problem is to represent each set with a doubly linked list like so: We may also have a data structure, such as a hash table mapping elements to pointers, that allows us to access each linked list node in constant time. We define rep[Si ] to be the element at the head of the list representing Si . Here are the algorithms for each operation: • M AKE -S ET(x) initializes x as a lone node. This takes Θ(1) time in the worst case. • F IND -S ET(x) walks left in the list containing x until it reaches the front of the list. This takes Θ(n) time in the worst case. • U NION(x, y) walks to the tail of Sx and to the head of Sy and concatenates the two lists together. This takes Θ(n) time in the worst case. 2.2 Augmenting the Linked List We can improve the behavior of our linked list solution by augmenting the linked lists such that each node has a pointer to its representative and that we also keep track of the tail of the list and the number of elements in the list at any time, which we will call its weight. Figure 2: An augmented linked list. Now, F IND -S ET(x) can run in Θ(1) time. Recitation 3: Union-Find and Amortization 3 We also change the behavior of U NION(x, y) to concatenate the lists containing x and y, up­ dating the rep pointers for all the elements in y. However, this could still require Θ(n) time in the worst case! Imagine if we called M AKE -S ET for every integer between 1 and n and then called U NION(n − 1, n), U NION(n − 2, n − 1), . . ., U NION(1, 2), where at the ith union we modify a list of length i. The total cost of all the calls to U NION is 1 + 2 + . . . + (n − 1) = Θ(n2 ). 3 First Improvement: Smaller into Larger (This part is updated and covered in Quiz 1 review session.) However, we can solve this by forcing U NION to merge the smaller list into the larger list. If we do this, the above scenario will only modify a list of length 1 every time, resulting in Θ(n) running time for these n − 1 U NIONs. Claim. With the first improvement, the amortized running time of n calls to M AKE -S ET followed by n calls to U NION is O(n lg n). Proof. We first use the aggregate method. Suppose the cost of moving a rep pointer is 1. Monitor some element x and the set Sx that contains it. After M AKE -S ET(x), we have weight[Sx ] = 1. When we call U NION(x, y), one of the following will happen: • If weight[Sx ] > weight[Sy ], then rep[x] stays unchanged, so we need not pay anything on x’s behalf, and weight[Sx ] will only increase. • If weight[Sx ] ≤ weight[Sy ], we pay 1 to update rep[x], and weight[Sx ] at least doubles. Sx can double at most lg n times, so we update rep[x] at most lg n times. Therefore across all the n elements, we get an amortized running time of O(n lg n). D Proof. The proof is very similar using the accounting method or the charging method. When we call U NION(x, y), suppose |Sx | < |Sy | without loss of generality. We will charge every element i ∈ Sx because their pointers rep[i]’s are updated. Similarly, each element i can be charged at most lg n times, because |Si | at least doubles. If we use the accounting method, each M AKE -S ET(x) stores lg n coins into the bank for use in future U NION. D Proof. Now we would like use the potential method. The potential method is usually the “in­ verse” of the accounting method. The potential function can be viewed as the balance in the bank account. In this case, we define the potential function to be lg n − lg |Si | Φ= i where the sum is taken over every element i in the structure (n is an upper bound on the total number of elements). 4 Recitation 3: Union-Find and Amortization When we call M AKE -S ET(x), |Sx | = 1, so the amortized cost is O(1) + ΔΦ = O(lg n). This means each M AKE -S ET(x) stores lg n coins into the bank. When we call U NION(x, y), again suppose |Sx | < |Sy |. The actual cost is |Sx |. ΔΦ < −|Sx |, because every element in i ∈ Sx now has |Si | doubled. This means we withdraw |Sx | coins from the bank to pay for this U NION operation. So the amortized cost of U NION is |Sx | + ΔΦ < 0. D 4 Forest of Trees Representation One interesting observation we can make is that we don’t really care about the links between nodes in the linked list; we only care about the rep pointers. Essentially, a list can be represented as a forest of trees, where rep[x] will be the root of the tree that contains x: Figure 3: A forest of trees representation of a disjoint set data structure. The algorithms will now be as follows: • M AKE -S ET(x) initializes x as a lone node. This takes Θ(1) time in the worst case. • F IND -S ET(x) climbs the tree containing x to the root. This takes Θ(height) time. • U NION(x, y) climbs to the roots of the trees containing x and y and merges sets the parent of rep[y] to rep[x]. This takes Θ(height) time. 4.1 Adapting the First Improvement Our first trick can be modified to fit the forest of trees representation by merging the tree with the smaller height into the tree with the bigger height. One can then show that the height of a tree will still be O(lg n). Recitation 3: Union-Find and Amortization 5 Figure 4: The data structure after calling U NION(x1 , y1 ). 5 Second Improvement: Path Compression Let’s now improve F IND -S ET. When we climb the tree, we learn the representatives of every inter­ mediate node we pass. Therefore we should redirect the rep pointers so a future call to F IND -S ET won’t have to do the same computations multiple times. Figure 5: The data structure after calling F IND -S ET(x8 ). Claim. Let n be the total number of elements we’re keeping track of. With the second improvement alone, the amortized running time of m operations (including F IND -S ET) is O(m lg n). Proof. Amortization by potential function. Let us define weight[xi ] to be the number of elements in the subtree rooted at xi . 6 Recitation 3: Union-Find and Amortization Figure 6: The same tree as in Figure 5, but redrawn. Notice that the xi ’s are much more compact than Figure 4. Let Φ(x1 , . . . , xn ) = i lg weight[xi ]. If U NION(xi , xj ) attaches xj ’s subtree’s root as a child of xi ’s subtree’s root, it only increases the weight of the root of Sxi . The increase is at most lg n, because there are only n elements at most. The weights of all the other elements stay unchanged. Now consider each step from child c to an ancestor p made by F IND -S ET(xi ) moves c’s subtree out of p’s subtree. If, at any particular step, weight[c] ≥ 12 weight[p], then the potential decreases by at least 1, which pays for the move. Furthermore, there can be at most lg n steps for which weight[c] < 12 weight[p], since each one decreases the size of the tree we’re looking in by more than half. D 6 Why Don’t We Do Both? If we do both improvements to the tree representation, we get spectacular behavior where the amortized cost of each operation is almost constant! 6.1 CLRS-Ackermann Function We define a function, Ak (j), with a similar structure to the well-known Ackermann function, as follows: Ak (j) = j+1 Aj+1 k−1 (j) if k = 0 if k ≥ 1 Because you’re repeatedly iterating Ak−1 many times when k ≥ 1, this function explodes very quickly: Recitation 3: Union-Find and Amortization A0 (1) A1 (1) A2 (1) A3 (1) = = = = 7 2 3 7 2047 A4 (1) > 22 .. . 22047 2048 Now consider its “inverse” as follows: α(n) = min{k : Ak (1) ≥ n} While not technically constant, this value is pretty darn close, even for very large values of n. For practical purposes, you can easily assume that α(n) ≤ 4. 6.2 How Spectacular? Theorem. With both improvements improvement, the amortized running time of m operations is O(mα(n)). The proof is very long and very tricky. If you’re interested, check out Section 21.4 in CLRS.