Give a tight asymptotic bound on the running time of the sequence of operations in Figure 21.3 assuming the linked-list representation and the weighted-union heuristic. (Introduction to Algorithm 21.2-4)
566 Chapter 21 Data Structures for Disioint Sets Number of objects updated Operation MAKE-SET(x1) MAKE-SET(2) MAKE-SET(xn) UNION(x2,x1) UNION(x3x2) UNION(x4,x3) UNION n-1) Figure 21.3 A sequence of 2n 1 operations o n objects that takes o(n2 time, or o(n) time per operation on average, using the linked-list set representation and the simple implementation of UNION. 11-1 The total number of operations is 2n-1, and so each operation on average requires o(n) time. That is, the amortized time of an operation is O(n). A weighted-union heuristic In the worst case, the above implementation of the UNION procedure requires an average of (n) time per call because we may be appending a longer list onto a shorter list; we must update the pointer to the set object for each member of the longer list. Suppose instead that each list also includes the length of the list (which we can easily maintain and that we always append the shorter list onto the longer, breaking ties arbitrarily. With this simple weighted-union heuristic, a sin- gle UNION operation can still take 20m) time if both sets have 2 (n) members. As the following theorem shows, however, a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, takes O(m n lg n) time Theorem 21.1 Using the linked-list representation of disjoint sets and the weighted-union heuris- tic, a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, takes O(m +nlgn) time. 566 Chapter 21 Data Structures for Disioint Sets Number of objects updated Operation MAKE-SET(x1) MAKE-SET(2) MAKE-SET(xn) UNION(x2,x1) UNION(x3x2) UNION(x4,x3) UNION n-1) Figure 21.3 A sequence of 2n 1 operations o n objects that takes o(n2 time, or o(n) time per operation on average, using the linked-list set representation and the simple implementation of UNION. 11-1 The total number of operations is 2n-1, and so each operation on average requires o(n) time. That is, the amortized time of an operation is O(n). A weighted-union heuristic In the worst case, the above implementation of the UNION procedure requires an average of (n) time per call because we may be appending a longer list onto a shorter list; we must update the pointer to the set object for each member of the longer list. Suppose instead that each list also includes the length of the list (which we can easily maintain and that we always append the shorter list onto the longer, breaking ties arbitrarily. With this simple weighted-union heuristic, a sin- gle UNION operation can still take 20m) time if both sets have 2 (n) members. As the following theorem shows, however, a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, takes O(m n lg n) time Theorem 21.1 Using the linked-list representation of disjoint sets and the weighted-union heuris- tic, a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, takes O(m +nlgn) time
