Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 99
Текст из файла (страница 99)
Noting thatthe actual cost of the MAKE-SET operation is O(1) completes the proof.Lemma 21.11The amortized cost of each LINK operation is O(α(n)).Proof Suppose that the qth operation is LINK(x, y). The actual cost of the LINK operation isO(1). Without loss of generality, suppose that the LINK makes y the parent of x.To determine the change in potential due to the LINK, we note that the only nodes whosepotentials may change are x, y, and the children of y just prior to the operation. We shall showthat the only node whose potential can increase due to the LINK is y, and that its increase is atmost α(n):••By Lemma 21.9, any node that is y's child just before the LINK cannot have itspotential increase due to the LINK.From the definition of φq(x), we see that, since x was a root just before the qthoperation, φq-1(x) = α(n) · rank[x].
If rank[x] = 0, then φq(x) = φq-1(x) = 0. Otherwise,φq(x) = (α(n) - level(x)) · rank[x] - iter(x)< α(n) · rank[x] (by inequalities (21.1) and (21.2)).•Because this last quantity is φq-1(x), we see that x's potential decreases.•Because y is a root prior to the LINK, φq-1(y) = α(n) · rank[y]. The LINK operationleaves y as a root, and it either leaves y's rank alone or it increases y's rank by 1.Therefore, either φq(y) = φq-1(y) or φq(y) = φq-1(y) + α(n).The increase in potential due to the LINK operation, therefore, is at most α(n).
The amortizedcost of the LINK operation is O(1) + α(n) = O(α(n)).Lemma 21.12The amortized cost of each FIND-SET operation is O(α(n)).Proof Suppose that the qth operation is a FIND-SET and that the find path contains s nodes.The actual cost of the FIND-SET operation is O(s). We shall show that no node's potentialincreases due to the FIND-SET and that at least max(0, s - (α(n) + 2)) nodes on the find pathhave their potential decrease by at least 1.To see that no node's potential increases, we first appeal to Lemma 21.9 for all nodes otherthan the root. If x is the root, then its potential is α(n) · rank[x], which does not change.Now we show that at least max(0, s - (α(n) + 2)) nodes have their potential decrease by atleast 1.
Let x be a node on the find path such that rank[x] > 0 and x is followed somewhere onthe find path by another node y that is not a root, where level(y) = level(x) just before theFIND-SET operation. (Node y need not immediately follow x on the find path.) All but atmost α(n) + 2 nodes on the find path satisfy these constraints on x. Those that do not satisfythem are the first node on the find path (if it has rank 0), the last node on the path (i.e., theroot), and the last node w on the path for which level(w) = k, for each k = 0, 1, 2, ..., α(n) - 1.Let us fix such a node x, and we shall show that x's potential decreases by at least 1.
Let k =level(x) = level(y). Just prior to the path compression caused by the FIND-SET, we havePutting these inequalities together and letting i be the value of iter(x) before path compression,we haveBecause path compression will make x and y have the same parent, we know that after pathcompression, rank[p[x]] = rank[p[y]] and that the path compression does not decreaserank[p[y]]. Since rank[x] does not change, after path compression we have that. Thus, path compression will cause either iter(x) to increase (to at least i+ 1) or level(x) to increase (which occurs if iter(x) increases to at least rank[x] + 1).
In eithercase, by Lemma 21.9, we have φq(x) ≤ φq-1(x) - 1. Hence, x's potential decreases by at least 1.The amortized cost of the FIND-SET operation is the actual cost plus the change in potential.The actual cost is O(s), and we have shown that the total potential decreases by at least max(0,s - (α(n) + 2)). The amortized cost, therefore, is at most O(s) - (s - (α(n) + 2)) = O(s) - s +O(α(n)) = O(α(n)), since we can scale up the units of potential to dominate the constanthidden in O(s).Putting the preceding lemmas together yields the following theorem.Theorem 21.13A sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKESET operations, can be performed on a disjoint-set forest with union by rank and pathcompression in worst-case time O(m α(n)).Proof Immediate from Lemmas 21.7, 21.10, 21.11, and 21.12.Exercises 21.4-1Prove Lemma 21.4.Exercises 21.4-2Prove that every node has rank at most ⌊lg n⌋.Exercises 21.4-3In light of Exercise 21.4-2, how many bits are necessary to store rank[x] for each node x?Exercises 21.4-4Using Exercise 21.4-2, give a simple proof that operations on a disjoint-set forest with unionby rank but without path compression run in O(m lg n) time.Exercises 21.4-5Professor Dante reasons that because node ranks increase strictly along a path to the root,node levels must monotonically increase along the path.
In other words, if rank(x) > 0 andp[x] is not a root, then level(x) ≤ level(p[x]). Is the professor correct?Exercises 21.4-6: ⋆Consider the function α'(n) = min {k : Ak (1) ≥ lg(n + 1)}. Show that α'(n) ≤ 3 for all practicalvalues of n and, using Exercise 21.4-2, show how to modify the potential-function argumentto prove that a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of whichare MAKE-SET operations, can be performed on a disjoint-set forest with union by rank andpath compression in worst-case time O(m α'(n)).Problems 21-1: Off-line minimumThe off-line minimum problem asks us to maintain a dynamic set T of elements from thedomain {1, 2, ..., n} under the operations INSERT and EXTRACT-MIN. We are given asequence S of n INSERT and m EXTRACT-MIN calls, where each key in {1, 2, ..., n} isinserted exactly once.
We wish to determine which key is returned by each EXTRACT-MINcall. Specifically, we wish to fill in an array extracted[1 m], where for i = 1, 2, ..., m,extracted[i] is the key returned by the ith EXTRACT-MIN call. The problem is "off-line" inthe sense that we are allowed to process the entire sequence S before determining any of thereturned keys.a.
In the following instance of the off-line minimum problem, each INSERT isrepresented by a number and each EXTRACT-MIN is represented by the letter E:4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5.Fill in the correct values in the extracted array.To develop an algorithm for this problem, we break the sequence S into homogeneoussubsequences. That is, we represent S byI1, E, I2, E, I3, ..., Im, E, Im+1,where each E represents a single EXTRACT-MIN call and each Ij represents a (possiblyempty) sequence of INSERT calls.
For each subsequence Ij, we initially place the keysinserted by these operations into a set Kj , which is empty if Ij is empty. We then do thefollowing.OFF-LINE-MINIMUM(m, n)1 for i ← 1 to n2do determine j such that iKj3if j ≠ m + 14then extracted[j] ← i5let l be the smallest value greater than jfor which set Kl exists6Kl ← KjKl, destroying Kj7 return extractedb. Argue that the array extracted returned by OFF-LINE-MINIMUM is correct.c. Describe how to implement OFF-LINE-MINIMUM efficiently with a disjoint-set datastructure. Give a tight bound on the worst-case running time of your implementation.Problems 21-2: Depth determinationIn the depth-determination problem, we maintain a forestoperations:•••of rooted trees under threeMAKE-TREE(v) creates a tree whose only node is v.FIND-DEPTH(v) returns the depth of node v within its tree.GRAFT(r, v) makes node r, which is assumed to be the root of a tree, become thechild of node v, which is assumed to be in a different tree than r but may or may notitself be a root.a.
Suppose that we use a tree representation similar to a disjoint-set forest: p[v] isthe parent of node v, except that p[v] = v if v is a root. If we implementGRAFT(r, v) by setting p[r] ← v and FIND-DEPTH(v) by following the findpath up to the root, returning a count of all nodes other than v encountered,show that the worst-case running time of a sequence of m MAKE-TREE,FIND-DEPTH, and GRAFT operations is Θ(m2).By using the union-by-rank and path-compression heuristics, we can reduce the worst-caserunning time. We use the disjoint-set forest, where each set Si (which is itself a tree)corresponds to a tree Ti in the forest . The tree structure within a set Si, however, does notnecessarily correspond to that of Ti. In fact, the implementation of Si does not record the exactparent-child relationships but nevertheless allows us to determine any node's depth in Ti.The key idea is to maintain in each node v a "pseudodistance" d[v], which is defined so thatthe sum of the pseudodistances along the path from v to the root of its set Si equals the depthof v in Ti.
That is, if the path from v to its root in Si is v0, v1, ..., vk, where v0 = v and vk is Si'sroot, then the depth of v in Ti is.b. Give an implementation of MAKE-TREE.c. Show how to modify FIND-SET to implement FIND-DEPTH. Your implementationshould perform path compression, and its running time should be linear in the lengthof the find path. Make sure that your implementation updates pseudodistancescorrectly.d.
Show how to implement GRAFT(r, v), which combines the sets containing r and v, bymodifying the UNION and LINK procedures. Make sure that your implementationupdates pseudodistances correctly. Note that the root of a set Si is not necessarily theroot of the corresponding tree Ti.e. Give a tight bound on the worst-case running time of a sequence of m MAKE-TREE,FIND-DEPTH, and GRAFT operations, n of which are MAKE-TREE operations.Problems 21-3: Tarjan's off-line least-common-ancestors algorithmThe least common ancestor of two nodes u and v in a rooted tree T is the node w that is anancestor of both u and v and that has the greatest depth in T. In the off-line least-commonancestors problem, we are given a rooted tree T and an arbitrary set P = {{u, v}} ofunordered pairs of nodes in T, and we wish to determine the least common ancestor of eachpair in P.To solve the off-line least-common-ancestors problem, the following procedure performs atree walk of T with the initial call LCA(root[T]).
Each node is assumed to be colored WHITEprior to the walk.LCA(u)1 MAKE-SET(u)2 ancestor[FIND-SET(u)] ← u3 for each child v of u in T4do LCA(v)5UNION(u, v)6ancestor[FIND-SET(u)] ← u7 color[u] ← BLACK8 for each node v such that {u, v}P9do if color[v] = BLACK10then print "The least common ancestor of"u "and" v "is" ancestor[FIND-SET(v)]a.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
