Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 96
Текст из файла (страница 96)
There are two varieties of relaxed heaps. One gives the sameamortized time bounds as Fibonacci heaps. The other allows DECREASE-KEY to run in O(1)worst-case (not amortized) time and EXTRACT-MIN and DELETE to run in O(lg n) worstcase time. Relaxed heaps also have some advantages over Fibonacci heaps in parallelalgorithms.See also the chapter notes for Chapter 6 for other data structures that support fastDECREASE-KEY operations when the sequence of values returned by EXTRACT-MIN callsare monotonically increasing over time and the data are integers in a specific range.Chapter 21: Data Structures for DisjointSetsSome applications involve grouping n distinct elements into a collection of disjoint sets.
Twoimportant operations are then finding which set a given element belongs to and uniting twosets. This chapter explores methods for maintaining a data structure that supports theseoperations.Section 21.1 describes the operations supported by a disjoint-set data structure and presents asimple application. In Section 21.2, we look at a simple linked-list implementation for disjointsets. A more efficient representation using rooted trees is given in Section 21.3. The runningtime using the tree representation is linear for all practical purposes but is theoreticallysuperlinear. Section 21.4 defines and discusses a very quickly growing function and its veryslowly growing inverse, which appears in the running time of operations on the tree-basedimplementation, and then uses amortized analysis to prove an upper bound on the runningtime that is just barely superlinear.21.1 Disjoint-set operationsA disjoint-set data structure maintains a collectionof disjoint dynamic sets.Each set is identified by a representative, which is some member of the set.
In someapplications, it doesn't matter which member is used as the representative; we only care that ifwe ask for the representative of a dynamic set twice without modifying the set between therequests, we get the same answer both times. In other applications, there may be aprespecified rule for choosing the representative, such as choosing the smallest member in theset (assuming, of course, that the elements can be ordered).As in the other dynamic-set implementations we have studied, each element of a set isrepresented by an object. Letting x denote an object, we wish to support the followingoperations:•••MAKE-SET(x) creates a new set whose only member (and thus representative) is x.Since the sets are disjoint, we require that x not already be in some other set.UNION(x, y) unites the dynamic sets that contain x and y, say Sx and Sy, into a new setthat is the union of these two sets.
The two sets are assumed to be disjoint prior to theoperation. The representative of the resulting set is any member of Sx Sy, althoughmany implementations of UNION specifically choose the representative of either Sx orSy as the new representative. Since we require the sets in the collection to be disjoint,we "destroy" sets Sx and Sy, removing them from the collection .FIND-SET(x) returns a pointer to the representative of the (unique) set containing x.Throughout this chapter, we shall analyze the running times of disjoint-set data structures interms of two parameters: n, the number of MAKE-SET operations, and m, the total number ofMAKE-SET, UNION, and FIND-SET operations.
Since the sets are disjoint, each UNIONoperation reduces the number of sets by one. After n - 1 UNION operations, therefore, onlyone set remains. The number of UNION operations is thus at most n - 1. Note also that sincethe MAKE-SET operations are included in the total number of operations m, we have m ≥ n.We assume that the n MAKE-SET operations are the first n operations performed.An application of disjoint-set data structuresOne of the many applications of disjoint-set data structures arises in determining theconnected components of an undirected graph (see Section B.4).
Figure 21.1(a), for example,shows a graph with four connected components.Figure 21.1: (a) A graph with four connected components: {a, b, c, d}, {e, f, g}, {h, i}, and{j}.(b) The collection of disjoint sets after each edge is processed.The procedure CONNECTED-COMPONENTS that follows uses the disjoint-set operationsto compute the connected components of a graph. Once CONNECTED-COMPONENTS hasbeen run as a preprocessing step, the procedure SAME-COMPONENT answers queries aboutwhether two vertices are in the same connected component.[1] (The set of vertices of a graphG is denoted by V [G], and the set of edges is denoted by E[G].)CONNECTED-COMPONENTS(G)1 for each vertex vV[G]2do MAKE-SET(v)3 for each edge (u, v)E[G]4do if FIND-SET(u) ≠ FIND-SET(v)5then UNION(u, v)SAME-COMPONENT(u, v)1 if FIND-SET(u) = FIND-SET(v)2then return TRUE3else return FALSEThe procedure CONNECTED-COMPONENTS initially places each vertex v in its own set.Then, for each edge (u, v), it unites the sets containing u and v.
By Exercise 21.1-2, after allthe edges are processed, two vertices are in the same connected component if and only if thecorresponding objects are in the same set. Thus, CONNECTED-COMPONENTS computessets in such a way that the procedure SAME-COMPONENT can determine whether twovertices are in the same connected component. Figure 21.1(b) illustrates how the disjoint setsare computed by CONNECTED-COMPONENTS.In an actual implementation of this connected-components algorithm, the representations ofthe graph and the disjoint-set data structure would need to reference each other. That is, anobject representing a vertex would contain a pointer to the corresponding disjoint-set object,and vice-versa.
These programming details depend on the implementation language, and wedo not address them further here.Exercises 21.1-1Suppose that CONNECTED-COMPONENTS is run on the undirected graph G = (V, E),where V = {a, b, c, d, e, f, g, h, i, j, k} and the edges of E are processed in the following order:(d, i), (f, k), (g, i), (b, g), (a, h), (i, j), (d, k), (b, j), (d, f), (g, j), (a, e), (i, d). List the vertices ineach connected component after each iteration of lines 3-5.Exercises 21.1-2Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices arein the same connected component if and only if they are in the same set.Exercises 21.1-3During the execution of CONNECTED-COMPONENTS on an undirected graph G = (V, E)with k connected components, how many times is FIND-SET called? How many times isUNION called? Express your answers in terms of |V|, |E|, and k.[1]When the edges of the graph are "static"-not changing over time-the connected componentscan be computed faster by using depth-first search (Exercise 22.3-11).
Sometimes, however,the edges are added "dynamically" and we need to maintain the connected components aseach edge is added. In this case, the implementation given here can be more efficient thanrunning a new depth-first search for each new edge.21.2 Linked-list representation of disjoint setsA simple way to implement a disjoint-set data structure is to represent each set by a linkedlist. The first object in each linked list serves as its set's representative. Each object in thelinked list contains a set member, a pointer to the object containing the next set member, and apointer back to the representative.
Each list maintains pointers head, to the representative, andtail, to the last object in the list. Figure 21.2(a) shows two sets. Within each linked list, theobjects may appear in any order (subject to our assumption that the first object in each list isthe representative).Figure 21.2: (a) Linked-list representations of two sets. One contains objects b, c, e, and h,with c as the representative, and the other contains objects d, f, and g, with f as therepresentative. Each object on the list contains a set member, a pointer to the next object onthe list, and a pointer back to the first object on the list, which is the representative. Each listhas pointers head and tail to the first and last objects, respectively. (b) The result ofUNION(e, g).
The representative of the resulting set is f.With this linked-list representation, both MAKE-SET and FIND-SET are easy, requiring O(1)time. To carry out MAKE-SET(x), we create a new linked list whose only object is x. ForFIND-SET(x), we just return the pointer from x back to the representative.A simple implementation of unionThe simplest implementation of the UNION operation using the linked-list set representationtakes significantly more time than MAKE-SET or FIND-SET. As Figure 21.2(b) shows, weperform UNION(x, y) by appending x's list onto the end of y's list.
We use the tail pointer fory's list to quickly find where to append x's list. The representative of the new set is the elementthat was originally the representative of the set containing y. Unfortunately, we must updatethe pointer to the representative for each object originally on x's list, which takes time linearin the length of x's list.In fact, it is not difficult to come up with a sequence of m operations on n objects that requiresΘ(n2) time.
Suppose that we have objects x1, x2, ..., xn. We execute the sequence of n MAKESET operations followed by n - 1 UNION operations shown in Figure 21.3, so that m = 2n - 1.We spend Θ(n) time performing the n MAKE-SET operations. Because the ith UNIONoperation updates i objects, the total number of objects updated by all n - 1 UNION operationsisOperationNumber of objectsupdatedMAKE-SET(x1)MAKE-SET(x2)11⋮MAKE-SET(xnUNION(x1, x2)UNION(x2, x3)UNION(x3, x4)⋮1123⋮UNION(xn-1, xn)⋮n-1Figure 21.3: A sequence of 2n - 1 operations on n objects that takes Θ(n2) time, or Θ(n) timeper operation on average, using the linked-list set representation and the simpleimplementation of UNION.The total number of operations is 2n - 1, and so each operation on average requires Θ(n) time.That is, the amortized time of an operation is Θ(n).A weighted-union heuristicIn 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 mustupdate the pointer to the representative for each member of the longer list.
Suppose insteadthat each list also includes the length of the list (which is easily maintained) and that wealways append the smaller list onto the longer, with ties broken arbitrarily. With this simpleweighted-union heuristic, a single UNION operation can still take Ω(n) time if both sets haveΩ(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 lgn) time.Theorem 21.1Using the linked-list representation of disjoint sets and the weighted-union heuristic, asequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SEToperations, takes O(m + n lg n) time.Proof We start by computing, for each object in a set of size n, an upper bound on the numberof times the object's pointer back to the representative has been updated.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
