6.046J Lecture 16: Disjoint-Set Data Structures

Lecture 16 Disjoint-Set Data Structures Supplemental reading in CLRS: Chapter 21 (§21.4 is optional) When implementing Kruskal’s algorithm in Lecture 4, we built up a minimum spanning tree T by adding in one edge at a time. Along the way, we needed to keep track of the connected components of T; this was achieved using a disjoint-set data structure. In this lecture we explore disjoint-set data structures in more detail. Recall from Lecture 4 that a disjoint-set data structure is a data structure representing a dynamic collection of sets S = {S 1 , . . . , S r }. Given an element u, we denote by S u the set containing u. We will equip each set S i with a representative element rep[S i ].1 This way, checking whether two elements u and v are in the same set amounts to checking whether rep[S u ] = rep[S v ]. The disjoint-set data structure supports the following operations: • M AKE -S ET(u): Creates a new set containing the single element u. – u must not belong to any already existing set – of course, u will be the representative element initially • F IND -S ET(u): Returns the representative rep[S u ]. • U NION(u, v): Replaces S u and S v with S u ∪ S v in S. Updates representative elements as appropriate. In Lecture 4, we looked at two different implementations of disjoint sets: doubly-linked lists and trees. In this lecture we’ll improve each of these two implementations, ultimately obtaining a very efficient tree-based solution. 16.1 Linked-List Implementation Recall the simple linked-list implementation of disjoint sets that we saw in Lecture 4: 1 This is not the only way to do things, but it’s just as good as any other way. In any case, we’ll need to have some symbol representing each set S i (to serve as the return value of F IND -S ET); the choice of what kind of symbol to use is essentially a choice of notation. We have chosen to use a “representative element” of each set rather than create a new symbol. Si : rep[S i ] u1 u2 u3 uk ··· M AKE -S ET(u) – initialize as a lone node Θ(1) F IND -S ET(u) – walk left from u until you reach the head of S u Θ(n) worst-case U NION(u, v) Θ(n) worst-case – walk right (towards the tail) from u and left (towards the head) from v. Reassign pointers so that the tail of S u and the head of S v become neighbors. The representative is updated automatically. Do we really need to do all that walking? We could save ourselves some time by augmenting each element u with a pointer to rep[S u ], and augmenting rep[S u ] itself with a pointer to the tail. That way, the running time of F IND -S ET would be O(1) and all the walking we formerly had to do in U NION would become unnecessary. However, to maintain the new data fields, U NION(u, v) would have to walk through S v and update each element’s “head” field to point to rep[S u ]. Thus, U NION would still take O(n) time in the worst case. Perhaps amortization can give us a tighter bound on the running time of U NION? At first glance, it doesn’t seem to help much. As an example, start with the sets {1} , {2} , . . . , { n}. Perform U NION(2, 1), followed by U NION(3, 1), and so on, until finally U NION(n, 1), so that S 1 = {1, . . . , n}. In each call to U NION, we have to walk to the tail of S 1 , which is continually growing. The ith call to U NION has to walk through i − 1 elements, so that the total running time of the n − 1 U NION operations is ¡ 2¢ Pn−1 i =1 (i − 1) = Θ n . Thus, the amortized cost per call to U NION is Θ(n). However, you may have noticed that we could have performed essentially the same operations more efficiently by instead calling U NION(1, 2) followed by U NION(1, 3), and so on, until finally U NION(1, n). This way, we never have to perform the costly operation of walking to the tail of S 1 ; we only ever have to walk to the tails of one-element sets. Thus the running time for this smarter sequence of n − 1 U NION operations is Θ(n), and the amortized cost per operation is O(1). The lesson learned from this analysis is that, when performing a U NION operation, it is best to always merge the smaller set into the larger set, i.e., the representative element of the combined set should be chosen equal to the representative of the larger constituent—that way, the least possible amount of walking has to occur. To do this efficiently, we ought to augment each S i with a “size” field, which we’ll call S i .weight (see Figure 16.1). It turns out that the “smaller into larger” strategy gives a significant improvement in the amortized worst-case running time of the U NION operation. We’ll show that the total running time of any sequence of U NION operations on a disjoint-set data structure with n elements (i.e., in which M AKE -S ET is called n times) is O(n lg n). Thus, the running time of m operations, n of which are M AKE -S ET operations, is ¡ ¢ O m + n lg n . To start, focus on a single element u. We’ll show that the total amount of time spent updating u’s “head” pointer is O(lg n); thus, the total time spent on all U NION operations is O(n lg n). When u is added to the structure via a call to M AKE -S ET, we have S u .weight = 1. Then, every time S u merges with another set S v , one of the following happens: Lec 16 – pg. 2 of 7 Si : head u1 u2 tail rep[S i ] u3 weight = 3 Figure 16.1. A linked list augmented with data fields for the head, the tail, and the size (weight). • S u .weight > S v .weight. Then no update to u’s “head” pointer is needed. • S v .weight ≥ S u .weight. Then, we update u’s “head” pointer. Also, in this case, the value of S u .weight at least doubles. Because S u .weight at least doubles every time we update u’s “head” pointer, and because S u .weight can only be at most n, it follows that the total number of times we update u’s “head” pointer is at most lg n. Thus, as above, the total cost of all U NION operations is O(n lg n) and the total cost of any sequence of m operations is O (m + n lg n). Exercise 16.1. With this new augmented structure, do we still need the list to be doubly linked? Which pointers can we safely discard? 16.2 Forest-of-Trees Implementation In addition to the linked-list implementation, we also saw in Lecture 4 an implementation of the disjoint-set data structure based on trees: u1 Si : rep[S i ] u4 u2 u5 u3 u6 M AKE -S ET(u) – initialize new tree with root node u Θ(1) F IND -S ET(u) – walk up tree from u to root Θ(height) = Θ(lg n) best-case U NION(u, v) O(1) + 2T F IND -S ET – change rep[S v ]’s parent to rep[S u ] The efficiency of the basic implementation hinges completely on the height of the tree: the shorter the tree, the more efficient the operations. As the implementation currently stands, the trees could Lec 16 – pg. 3 of 7 u v v.rank u.rank Figure 16.2. Union by rank attempts to always merge the shorter tree into the taller tree, using rank as an estimate (always an overestimate) of height. be unbalanced and F IND -S ET could take as long as Θ(n) in the worst case. However, this behavior can be dramatically improved, as we will see below. 16.2.1 Union by rank When we call U NION(u, v), rep[S v ] becomes a child of rep[S u ]. Merging S v into S u in this way results in a tree of height © ª max height[S u ], height[S v ] + 1 (16.1) (why?). Thus, the way to keep our trees short is to always merge the shorter tree into the taller tree. (This is analogous to the “smaller into larger” strategy in the linked-list implementation.) To help us do this, we will introduce a new data field called rank. If u is the root of a tree (i.e., if u = rep[S u ]), then u.rank will be an upper bound on the height of S u .2 In light of (16.1), the pseudocode for U NION will be as follows (see Figure 16.2): Algorithm: U NION( u e, ve) 1 2 3 4 5 6 7 8 9 u ← F IND -S ET( u e) v ← F IND -S ET(ve) if u.rank = v.rank then u.rank ← u.rank + 1 v.parent ← u else if u.rank > v.rank then v.parent ← u else u.parent ← v The following lemma shows that U NION preserves the fact that rank is an upper bound on height. Lemma 16.1. Suppose initially the following hold: • S u 6= S v 2 If union by rank is the only improvement we use, then u.rank will actually be the exact height of S . But in general, u we wish to allow other improvements (such as path compression) to decrease the height of S u without having to worry about updating ranks. In such cases, the upper bound provided by u.rank may not be tight. Lec 16 – pg. 4 of 7 • S u has height h 1 and S v has height h 2 • rep[S u ].rank = r 1 and rep[S v ].rank = r 2 • h 1 ≤ r 1 and h 2 ≤ r 2 . Suppose we then call U NION(u, v), producing a new set S = S u ∪ S v . Let h be the height of S and let r = rep[S].rank. Then h ≤ r. Proof. First, suppose r 1 > r 2 . Then S v has been merged into S u and r = r 1 . By (16.1), we have © ª h = max h 1 , h 2 + 1 © ª ≤ max r 1 , r 2 + 1 = r1 = r. A similar argument shows that h ≤ r in the case that r 2 > r 1 . Finally, suppose r 1 = r 2 . Then S v has been merged into S u and r = r 1 + 1 = r 2 + 1, so © ª h = max h 1 , h 2 + 1 © ª ≤ max r 1 , r 2 + 1 = r2 + 1 = r. It turns out that the rank of a tree with k elements is always at most lg k. Thus, the worst-case performance of a disjoint-set forest with union by rank having n elements is M AKE -S ET F IND -S ET U NION O(1) Θ(lg n) Θ(lg n). Exercise 16.2. Amortization does not help this analysis. Given sufficiently large n and given m which is sufficiently large compared to n, produce a sequence of m operations, n of which are M AKE -S ET operations (so the structure ultimately contains n elements), whose running time is Θ(m lg n). Exercise 16.3. Above we claimed that the rank of any tree with k elements is at most lg k. Use induction to prove this claim. (You may assume that U NION is the only procedure that modifies ranks. However, you should not assume anything about the height of a tree except that it is less than the rank.) What is the base case? 16.2.2 Path compression The easiest kind of tree to walk up is a flat tree, where all non-root nodes are direct children of the root (see Figure 16.3). The idea of path compression is that, every time we invoke F IND -S ET and walk up the tree, we should reassign parent pointers to make each node we pass a direct child of the root (see Figure 16.4). This locally flattens the tree. With path compression, the pseudocode for F IND -S ET is as follows: Lec 16 – pg. 5 of 7 u1 u4 u2 u5 u6 u3 Figure 16.3. In a flat tree, each F IND -S ET operation requires us to traverse only one edge. u1 u1 u2 u4 u3 u5 u6 u2 u3 u7 u6 u9 u8 u7 u4 u9 u5 u8 Figure 16.4. With path compression, calling F IND -S ET (u 8 ) will have the side-effect of making u 8 and all of its ancestors direct children of the root. Algorithm: F IND -S ET(u) 1 2 3 4 5 6 7 8 A←; n←u while n is not the root do A ← A ∪ { n} n ← n.parent for each x ∈ A do x.parent ← n return n What data structure should we use for A? In an ideal world, where n can truly be arbitrarily large, we would probably want A to be a dynamically doubled array of the kind discussed in Lecture 10. In real life, however, some assumptions can be made. For example, if you have less than a petabyte (1024 TB, or 253 bits) of available memory, then the rank (and therefore the height) of any tree is at ¡ ¢ most lg 253 = 53, and it would be slightly more efficient to maintain A as a static array of size 53 (with an end-marking sentinel value, perhaps). It can be shown that, with path compression (but not union by rank), the running time of any sequence of n M AKE -S ET operations, f F IND -S ET operations, and up to n − 1 U NION operations is ¡ ¡ ¢¢ Θ n + f 1 + log2+ f /n n . 16.2.3 Both improvements together The punch-line of this lecture is that, taken together, union by rank and path compression produce a spectacularly efficient implementation of the disjoint-set data structure. Lec 16 – pg. 6 of 7 Theorem 16.2. On a disjoint-set forest with union by rank and path compression, any sequence of m operations, n of which are M AKE -S ET operations, has worst-case running time ¡ ¢ Θ mα(n) , where α is the inverse Ackermann function. Thus, the amortized worst-case running time of each operation is Θ (α(n)). If one makes the approximation α(n) = O(1), which is valid for literally all conceivable purposes, then the operations on a disjoint-set forest have O(1) amortized running time. The proof of this theorem is in §21.4 of CLRS. You can read it if you like; it is not essential. You might also be interested to know that, in a 1989 paper, Fredman and Saks proved that Θ (α(n)) is the fastest possible amortized running time per operation for any implementation of the disjoint-set data structure. The inverse Ackermann function α is defined by © ª α(n) = min k : A k (1) ≥ n , where (k, j) 7→ A k ( j) is the Ackermann function. Because the Ackermann function is an extremely rapidly growing function, the inverse Ackermann function α is an extremely slowly growing function (though it is true that limn→∞ α(n) = ∞). The Ackermann function A (at least, one version of it) is defined by ( A k ( j) = j+1 ( j +1) A k−1 ( j) if k = 0 (that is, A k−1 iterated j + 1 times) for k ≥ 1. Some sample values of the Ackermann function are A 1 (1) = 3 A 1 ( j) = 2 j + 1 A 2 (1) = 7 A 2 ( j) = 2 j+1 ( j + 1) A 3 (1) = 2047 A 4 (1) À 1080 . By current estimates, 1080 is roughly the same order of magnitude as the number of particles in the observable universe. Thus, even if you are a theoretical computer scientist or mathematician, you will still most likely never end up considering a number n so large that α(n) > 4. Exercise 16.4. Write down a sequence of operations on the disjoint-set forest with union by rank and path compression (including M AKE -S ET operations) which cause a taller tree to be merged into a shorter tree. Why do we allow this to happen? Lec 16 – pg. 7 of 7