《算法设计技巧与分析课件(英文版)：ch4 Heaps and the disjoint sets data structures》由会员分享，可在线阅读，更多相关《算法设计技巧与分析课件(英文版)：ch4 Heaps and the disjoint sets data structures（67页珍藏版）》请在金锄头文库上搜索。
1、Algorithms Design Techniques and AnalysisChapter 4Heaps and the disjoint sets data structuresAlgorithms Design Techniques and AnalysisWhat we have known after previous learningThe choice of data structure can influence the design of an efficient algorithm significantly.Some elementary data structure
2、s:Linked lists (circular list, doubly linked list, circular doubly linked list)Stacks and queuesGraphs (planar graph)Trees, rooted trees, binary trees, binary search treesAlgorithms Design Techniques and AnalysisContents of current chapter Heaps Operations on heaps (sift-up, sift-down, insert, delet
3、e)Creating a heapHeapsortMin and max heapsDisjoint sets data structuresRepresentationUnion-find algorithmsAnalysis of union-find algorithmsAlgorithms Design Techniques and Analysis4.2 Heaps Why need heaps? In many algorithms, there is the need for a data structure that supports the two operations: i
4、nsert an element and find the element of maximum value.For a regular queue, finding the largest element is expensive;For a sorted array, insertion is expensive;A priority queue supports both operations, an efficient implementation of such structure is to use a heap.Algorithms Design Techniques and A
5、nalysis4.2 Heaps - contd What is a heap?Definition 4.1 A (binary) heap is an almost-complete binary tree with each node satisfying the heap property: If v and p(v) are a node and its parent, respectively, then the key of the item stored in p(v) is not less than the key of the item stored in v.Algori
6、thms Design Techniques and Analysis Are they are heaps or not?1.A null tree ( )2.A single node tree ( )3. ( )4. ( )20945101737 XAlgorithms Design Techniques and AnalysisRepresentation of a heapA heap T with n nodes can be represented by an array H1.n in the following way:The root of T is stored in H
7、1.Suppose that a node x in T is stored in Hj. If it has a left child, then this child is stored in H2j. If it (also) has a right child, then this child is stored in H2j+1.The parent of element Hj that is not the root of the tree is stored in Hj/2.Algorithms Design Techniques and Analysis759354111017
8、20123456791081234567891020179101145375EndAlgorithms Design Techniques and Analysis Observations from the representationThe heap property implies that the keys of the elements along every path from the root to a leaf are arranged in nonincreasing order.A heap is in fact an array H1.n with the propert
9、y that for any index j, 2jn, key(Hj/2)key(Hj). We note that if the tree nodes are numbered from 1 to n in a top-down and left to right manner, then each entry Hi is represented in the corresponding tree by the node numbered i.Algorithms Design Techniques and AnalysisSupported operations of a heap da
10、ta structuredelete-maxH: delete and return an item of maximum key from nonempty heap H.insertH,x: insert item x into heap H.deleteH,i: delete the ith item from heap H.makeheapA: transform array A into a heap.Algorithms Design Techniques and Analysis4.2.1 Operations on heapsSift-upSift-downInsertDele
11、teDelete-maxAlgorithms Design Techniques and AnalysisSift-up When to use? Suppose that for some i1, the key of the element stored in H i of the heap is changed to an element whose key is greater than the key of its parent. This violates the heap property and, consequently, the data structure is no l
12、onger a heap. The sift-up operation moves H i up along the unique path from Hi to the root until its proper location along this path is found. At each step along the path, the key of H i is compared with the key of its parent Hi/2.Algorithms Design Techniques and Analysis Procedure SIFT-UPInput: An
13、array H1n and an index i between 1 and n.Output : Hi is moved up, if necessary, so that it is not larger than its parents. 1. donefalse 2. if i=1 then exit node i is the root 3. repeat 4. if key (Hi)key(H i/2) then interchange Hi and H i/2 5. else donetrue 6. i i/2 7. until i=1 or doneAlgorithms Des
14、ign Techniques and Analysis An example 310945725112517252025111720EndAlgorithms Design Techniques and AnalysisSift-down When to use? Suppose that for some in then exit node i is a leaf 3. repeat 4. i2i 5. if i+1 n and key(Hi+1)key(Hi) then ii+1 6. if key(H i/2)n or doneAlgorithms Design Techniques a
15、nd Analysis An example201094537511331135EndAlgorithms Design Techniques and AnalysisInsertBasic idea: To insert an element x into a heap H, append x to the end of H after its size has been increased by 1, and then sift x up, if necessary, until the heap property is satisfied.Algorithm 4.1 INSERTInpu
16、t: A heap H1n and a heap element x.Output: A new heap H1n+1 with x being one of its elements. 1. nn+1 increase the size of H 2. Hnx 3. SIFT-UP(H,n)Time complexity O(logn)Algorithms Design Techniques and AnalysisDeleteBasic idea: To delete an element Hi from a heap H of size n, replace Hi by Hn, decr
17、ease the heap size by 1, and then sift Hi up or down, if necessary, depending on the value of its key relative to the keys stored in its parent and children nodes, until the heap property is satisfied.Algorithms Design Techniques and Analysis Algorithm 4.2 DELETEInput: A nonempty heap H1n and an ind
18、ex i between 1 and n.Output: A new heap H1n-1 after Hi is removed. 1. xHi; yHn 2. nn-1 decrease the size of H 3. if i=n+1 then exit done 4. Hiy 5. if key(y) key(x) then SIFT-UP(H,i) 6. else SIFT-DOWN(H,i) 7. end ifTime complexity O(logn).Algorithms Design Techniques and AnalysisDelete-maxBasic idea:
19、 This operation deletes and returns an item of maximum key in a nonempty heap H: simply return the element stored in the root and delete it from the heap.Algorithm 4.3 DELETEMAXInput: A heap H1n.Output: An element x of maximum key is returned and deleted from the heap.1. xH12. DELETE(H,1)3. return x
20、Time complexity O(logn)Algorithms Design Techniques and Analysis4.2.2 Creating a heapMethod 1: Given an array A1.n of n elements, it is easy to construct a heap out of these elements by starting from an empty heap and successively inserting each element until A is transformed into a heap. Transform
21、the array A1.10=4,3,8,10,11,13,7,30,17,26 into a heap.Time complexity: Since inserting the jth key costs O(logj), the time complexity is O(nlogn). (see example 1.12, p.30 or p17)Algorithms Design Techniques and Analysis4.2.2 Creating a heap - contdMethod 2: Transform an almost-complete binary tree T
22、 with n nodes into a heap H1.n: starting from the last node (the one numbered n) to the root (node number 1), we scan all these nodes one by one, each time transforming, if necessary, the subtree rooted at the current node into a heap. The elements An/2+1,A n correspond to the leaves of T ( ), and t
23、herefore we may start adjusting array at An/2 and continue the adjustment at An/2-1,A1. Algorithms Design Techniques and Analysis108 1113730172612345678910Transform the array A1.10=4,3,8,10,11,13,7,30,17,26 into a heap. An example43EndAlgorithms Design Techniques and Analysis Algorithm 4.4 MAKEHEAP
24、Input: An array A1n of n elements.Output: A1n is transformed into a heap. 1. for i n/2 downto 1 2. SIFT-DOWN(A, i) 3. end forAlgorithms Design Techniques and AnalysisAlgorithm analysis of MAKEHEAPLet T be the almost-complete binary tree corresponding to the array A1.n. Then the height of T is k = lo
25、gn (by observation 3.4, p.111, or p72).Let Aj corresponds to the jth node in level i of T, the number of iterations excuted by SHFT-DOWN(A,j) is at most k-i.The are exactly 2i nodes on level i (0ik), so the total number of iterations is at most:Algorithms Design Techniques and AnalysisAlgorithm anal
26、ysis of MAKEHEAPThe are at most two element comparisons in each iteration of SIFT-DOWN.Thus, the total number of element comparisons is at most 4n.There is at least one iteration in each call to SIFT-DOWN, so the minimum number of element comparisons is 2n/2n-1. Theorem 4.1 Let C(n) be the number of
27、 element comparisons performed by Algorithm MAKEHEAP for the construction of a heap of n elements. Then, n-1 C(n) 4n.Time complexity: (n), Space complexity: (1)Algorithms Design Techniques and Analysis4.2.3 Heapsort Basic ideaGiven an array A1n, Transform A into a heap with the property that the key
28、 of each element is the element itself, i.e., key(Ai)=Ai.Since the maximum of the entries in A is now stored in A1, interchange A1 and An so that An is the maximum element in the array. Now, the element stored in A1 may be smaller than the element stored in one of its children. Therefore, use Proced
29、ure SIFT-DOWN to transform A1n-1 into a heap.Interchange A1 with An-1 and adjust the array A1n-2 into a heap.The process of exchanging elements and adjusting heaps is repeated until the heap size becomes 1, at which point A1 is minimum.Algorithms Design Techniques and Analysis Algorithm 4.5 HEAPSORT
30、Input: An array A1n of n elements.Output: Array A sorted in nondecreasing order. 1. MAKEHEAP(A) 2. for jn downto 2 3. interchange A1 and Aj 4. SIFT-DOWN(A1j-1,1) 5. end forAlgorithms Design Techniques and AnalysisSort the array A1.10=4,3,8,10,11,13,7,30, 17,26 in non-descending order. An example108
31、1113730172612345678910431234567891026438101113730171713 11871034123456789103026123456789104302613171187103Algorithms Design Techniques and AnalysisSort the array A1.10=4,3,8,10,11,13,7,30, 17,26 in non-descending order. An example1713 11871033012345678910426123456789103042613171187103Algorithms Desi
32、gn Techniques and AnalysisSort the array A1.10=4,3,8,10,11,13,7,30, 17,26 in non-descending order. An example1713 118710330123456789104261234567891030426131711871031013 11874330123456789102617123456789103026171310118743Algorithms Design Techniques and AnalysisAlgorithm analysisSpace: The algorithm s
33、orts in place, i.e., it needs no auxiliary storage. Time: Creating heap by MAKEHEAP costs (n) time.SIFT-DOWN costs O(logj) and repeat n-1 times. Theorem 4.2 Algorithm HEAPSORT sorts n elements in O(nlogn) time and (1) space.Algorithms Design Techniques and Analysis4.2.4 Min and max heapMax-heaps: th
34、e heap property mandates that the key of the element stored in a node other than the root is less than or equal to the key of the element stored in its parent.Min-heaps: the heap property mandates that the key of the element stored in a node other than the root is greater than or equal to the key of
35、 the element stored in its parent.Algorithms Design Techniques and AnalysisA1.10=4,3,8,10,11,13,7,30,17,26 into a heap. An example1713 11871034123456789103026Max heap107 111383017261234567891034Min heapAlgorithms Design Techniques and Analysis4.3 Disjoint sets data structuresWhat are disjoint sets?
36、Suppose we are given a set S of n distinct elements. The elements are partitioned into disjoint sets. In each subset, a distinguished element will serve as the name of the set or set representative. For example, if S=1,2,11 and there are 4 subsets 1,7,10,11, 2,3,5,6, 4,8 and 9, these subsets may be
37、labeled as 1,3,8, and 9, in this order. Algorithms Design Techniques and AnalysisTwo operations on disjoint setsFIND(x): Find and return the name of the set containing x.UNION(x,y): Replace the two sets containing x and y by their union. The name of the union set is either the name of the old set co
38、ntaining x or the name of the old set containing y; it will be determined later. For example, if S=1,2,11 and there are 4 subsets 1,7,10,11, 2,3,5,6, 4,8 and 9, these subsets are labeled as 1,3,8, and 9.FIND(11) returns 1;UNION(1,3) returns a new subset labeled as 1 or 3Algorithms Design Techniques
39、and Analysis What is our goal?For algorithms that need a sequence of m union and find operations, we should design efficient algorithms for above two operations.How do we design the data structure that is both simple and leads to efficient implementation of these two operations?How to represent a se
40、t?Algorithms Design Techniques and AnalysisBit vector representation?Suppose there are n distinct elements in S, then a subset of S is represented as a bit vector SET1.n, where SETi=1 if the ith element of S is in the subset, otherwise, SETi=0. For example, S=1,2,11 and 4 subsets S1=1,7,10,11, S2=2,
41、3,5,6, S3=4,8 and S4=9, S1=10000010011; S2=01101100000; S3=00010001000; S4=00000000100Problems: too many extra space resources; time of union operation is proportional to n rather than the sizes of two subsetsAlgorithms Design Techniques and AnalysisList representation?The subset is represented as a
42、 list of its elements. For example, S=1,2,11 and 4 subsets S1=1,7,10,11, S2=2,3,5,6, S3=4,8 and S4=9Problems: For non-sorted lists, the time of union operation is proportional to the multiply of the sizes of two subsets; For sorted lists, the time of union operation is proportional to the sum of siz
43、es of two subsets.Algorithms Design Techniques and AnalysisTree representationTo represent each set as a rooted tree with data elements stored in its nodes. Each element x other than the root has a pointer to its parent p(x) in the tree. The root has a null pointer, and it serves as the name or set
44、representative of the set.Notation:Root(x) denote the root of the tree containing x. Thus:FIND(x) always returns root(x);UNION(x,y) actually means UNION(root(x), root(y).1234567891011Algorithms Design Techniques and Analysisrepresentation of the treesA subset is represented as a tree, all disjoint s
45、ubsets are a forest.If we assume that the elements are the integer 1,2,n, the forest can conveniently be represented by an array A1.n such that Aj is the parent of element j. The null parent can be represented by the number 0.1234567891011Algorithms Design Techniques and Analysis An example of the r
46、epresentation 12345678910110 3 0 8 2 2 100 111 23456789 10 11EndAlgorithms Design Techniques and AnalysisStraightforward implementationFIND(x): Simply follow the path from x until the root is reached, then return root(x).UNION(x,y):Let the link of root(x) point to root(y), i.e., if root(x) is u and
47、root(y) is v, then let v be the parent of u.Algorithms Design Techniques and Analysisprocedure FIND(X)Input: A node x.Output: root(x), the root of the tree containing x.1. yx2. while p(y) null Find the root of the tree containing x3. yp(y)4. end while5. return y;Procedure UNION(x,y)Input: Two elemen
48、ts x and y.Output: The union of the two trees containing x and y. The original trees are destroyed 1. uFIND(x); vFIND(y) 2. p(u) v;Algorithms Design Techniques and AnalysisAre they useful?Consider the disjoint sets 1,2,n and the operations UNION(1,2), FIND(1), UNION(2,3), FIND(1), UNION(3,4), FIND(1
49、), UNION(4,5),FIND(1), UNION(n-1,n), FIND(1).We will get the result on the right:nn-11The last find operation requires n times.Can we constraint the height of each tree?Algorithms Design Techniques and Analysis4.3.1 The union by rank heuristicIn order to constraint the height of each tree, we adopt
50、the union by rank heuristic. Basic idea of union by rankwe store with each node a nonnegative number referred to as the rank of that node. The rank of a node is essentially its height.Let x and y be two roots of two different trees in the current forest. Initially, each node has rank 0. when perform
51、ing the operation UNION(x,y), we compare rank(x) and rank(y).If rank(x)rank(y), we make x the parent of y.Otherwise, if rank(x)=rank(y), we make y the parent of x and increase rank(y) by one.Algorithms Design Techniques and Analysis An examplen12start213nUNION(1,2)2134nUNION(2,3)2145nUNION(FIND(3),4
52、)32134nUNION(FIND(n-1),n)The result is much better than Straightforward method.Algorithms Design Techniques and AnalysisTwo fundamental observationsLet x be any node, p(x) be the parent of x, we have Observation 4.1rank(p(x) rank(x)+1. Observation 4.2The value of rank(x) is initially zero and increa
53、ses in subsequent union operations until x is no longer a root. Once x becomes a child of another node, its rank never changes. Algorithms Design Techniques and Analysis LemmaLemma 4.1 The number of nodes in a tree (formed via union by heuristic) with root x is at least 2rank(x).Proof: by induction
54、on the number of union operations.(1)Initially, x is a tree by itself and its rank is zero, the lemma holds;(2)Let x and y be two roots, and consider the operation UNION(x,y). Assume that the lemma holds before this operation;(3)If rank(x)rank(y), then the formed tree rooted at y (x) has more nodes
55、than the old tree with root y (x) and its rank is unchanged. Thus, if rank(x)rank(y), the lemma holds after the operation; If rank(x)=rank(y), by induction, the formed tree with root y has at least 2rank(x) +2rank(y)= 2rank(y)+1 nodes. Since rank(y) will be increased by one, the lemma holds after th
56、e operation.Algorithms Design Techniques and AnalysisAlgorithm analysisThe cost of each find operation is O(logn).By Lemma 4.1, if the number of nodes in the tree rooted as x is k, then the height of that tree is at most logk.The time required by UNION(x,y) is O(1) if both x and y are roots, otherwi
57、se, the running time reduces to that of the find operation, which is O(logn);Algorithms Design Techniques and AnalysisAlgorithm analysis Conclusion: Using the union by rank heuristic, the time complexity of a sequence of m interspersed union and find instructions is O(mlogn).Can we enhance the perfo
58、rmance of the find operation further?Algorithms Design Techniques and Analysis4.3.2 Path compressionTo enhance the performance of the find operation further, another heuristic known as path compression is employed.In a FIND(x) operation, after the root y is found, we traverse the path from x to y on
59、e more time and change the parent pointers of all nodes along the path to point directly to y.Algorithms Design Techniques and Analysis An example12341432Execute the find operation FIND(4) with path compressionAlgorithms Design Techniques and Analysis4.3.3 The union-find algorithmsAlgorithms 4.6 FIN
60、DInput: A node x.Output: root(x), the root of the tree containing x. 1. yx 2. while p(y) null Find the root of the tree containing x 3. yp(y) 4. end while 5. rooty; yx 6. while p(y) null Do path compression 7. wp(y); p(y)root; yw 8. end while 9. return rootAlgorithms Design Techniques and AnalysisAl
61、gorithm 4.7 UNIONInput: Two elements x and y.Output: The union of the two trees containing x and y. The original trees are destroyed1. uFIND(x); vFIND(y)2. if rank(u) rank(v) then3. p(u)v4. if rank(u) =rank(v) then rank(v)rank(v)+1 5. else p(v)u6. end if4.3.3 The union-find algorithmsAlgorithms Desi
62、gn Techniques and Analysis An exampleLet S=1,2,9 and consider applying the following sequence of unions and finds: UNION(1,2), UNION(3,4), UNION(5,6), UNION(7,8), UNION(2,4), UNION(8,9), UNION(6,8), FIND(5), UNION(4,8), FIND(1).Algorithms Design Techniques and Analysis An example246891357UNION(3,4)U
63、NION(5,6)UNION(7,8)S1,2,3,4,5,6,7,8,9UNION(1,2)Algorithms Design Techniques and Analysis An example246891357UNION(2,4)UNION(8,9)UNION(6,8)Algorithms Design Techniques and Analysis An example246891357FIND(5)Algorithms Design Techniques and Analysis An example246891357UNION(4,8)Algorithms Design Techn
64、iques and Analysis An example246891357FIND(1)EndAlgorithms Design Techniques and Analysis4.3.4 Analysis of the union-find algorithmsLemma 4.2 For any integer r0, the number of nodes of rank r is at most n/2r.Proof: Fix a particular of r.When a node x is assigned a rank of r, label by x all the nodes
65、 contained in the tree rooted at x. By Lemma 4.1, the number of labeled nodes is at least 2r.If the root of that tree changed, then the rank of the root of the new tree is at least r+1. This means that those nodes labeled with x will never be labeled again.The maximum number of nodes labeled is n, a
66、nd each root of rank r has at least 2r nodes, so there are at most n/2r nodes with rank r.Algorithms Design Techniques and Analysis4.3.4 Analysis of the union-find algorithms Corollary 4.1 The rank of any node is at most logn. Proof: if for some node x, rank(x)=r logn+1, then by Lemma 4.2, there are
67、 at most n/2 logn+11 nodes of rank r. this is a contradiction. Definition 4.2 For any positive integer n, log*n is defined as For example, log*2=1, log*4=2, log*16=3, log*65536=4, log*265536=5.Algorithms Design Techniques and AnalysisAlgorithm analysis Theorem 4.3 Let T(m) denote the running time re
68、quired to process an interspersed sequence of m union and find operations using union by rank and path compression. Then T(m)=O(mlog*n) in the worst case.Note that for almost all practical purposes, log*n5. this means the running time is O(m) for virtually all practical applications.Algorithms Desig
69、n Techniques and AnalysisConclusion In this chapter, two major data structures that are more sophisticated than those in the former chapter are introduced:Heaps and the operations on heaps:Adjust the heap (sift-up, sift-down)Make a heap (sift-down)Disjoint sets data structuresRepresentationUnion-fin
70、d algorithmsAnalysis of union-find algorithmsAlgorithms Design Techniques and AnalysisExercises4.34.74.114.26Design and implement algorithms Insert, Delete, Makeheap for minimal heap;Design and implement Heapsort1 algorithm based on minmal heap to sort an array in nonascending order;Implement algorithm 4.6 and 4.7, test the implementation on example 4.4
