01算法設(shè)計第四講

1、Algorithms Design Techniques and Analysis第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu)Algorithms Design Techniques and Analysis本章內(nèi)容堆 堆上的運算(sift-up, sift-down, insert, delete)創(chuàng)建堆堆排序最小堆和最大堆不相交集數(shù)據(jù)結(jié)構(gòu)RepresentationUnion-find 算法union-find 算法的分析Algorithms Design Techniques and Analysis4.2 堆 為什么需要堆? 在很多算法中，需要支持下面兩種運算的數(shù)據(jù)結(jié)構(gòu)：插入元素和尋找最大元素 。使用

2、普通隊列，尋找最大元素需要搜索整個隊列，開銷比較大。采用排序數(shù)組，插入運算需要移動很多元素，開銷也會比較大。優(yōu)先隊列使用堆作為數(shù)據(jù)結(jié)構(gòu)，更加有效的支持插入和尋找最大值元素這兩種運算，QAAlgorithms Design Techniques and Analysis4.2 堆 - contd 什么是堆?定義 4.1 一個（二叉）堆是一個幾乎完全的二叉樹，它的每個節(jié)點都滿足堆的特性：如果v和p(v)分別是節(jié)點和它的父節(jié)點，那么存儲在p(v)中的數(shù)據(jù)項鍵值不小于存儲在v中數(shù)據(jù)項的鍵值。QAlgorithms Design Techniques and Analysis 下面哪些是堆?空樹 ( )

3、單節(jié)點樹 ( ) ( ) ( )2094510937XAlgorithms Design Techniques and Analysis堆的表示方式一個有n個節(jié)點的堆T，可以由一個數(shù)組H1.n 用下面的方式表示：T的根節(jié)點存儲在H1中假設(shè)T的節(jié)點x存儲在Hj中，如果它有左子節(jié)點，這個子節(jié)點存儲在H2j中；如果它也有右子節(jié)點，這個子節(jié)點存儲在 H2j+1中元素Hj的父節(jié)點如果不是根節(jié)點，則存儲在Hj/2中Algorithms Design Techniques and Analysis75935411101720123456791081234567891020179101145375EndAlg

4、orithms Design Techniques and Analysis 堆的特性堆的特性蘊(yùn)含著:沿著每條從根到葉子的路徑，元素的鍵值以非升序排列。因此堆可以看做是二叉樹，而它實質(zhì)上是一個數(shù)組H1.n 。它有如下性質(zhì):對于任何索引j, 2jn, key(Hj/2)key(Hj)。如果樹的節(jié)點以自頂向下、從左到右的方法，按1到n的順序編號，那么，每一項Hi在對應(yīng)的樹中表示成編號為i的節(jié)點Algorithms Design Techniques and Analysis堆數(shù)據(jù)結(jié)構(gòu)支持的運算delete-maxH:從一個非空的堆H中刪除最大鍵值的數(shù)據(jù)項并將數(shù)據(jù)項返回。insertH,x:插入項x

5、到堆H中。deleteH,i:從堆H中刪除第i項。makeheapA:將數(shù)組A轉(zhuǎn)換成堆。Algorithms Design Techniques and Analysis4.2.1 堆上的運算Sift-upSift-downInsertDeleteDelete-maxAlgorithms Design Techniques and AnalysisSift-up 什么時候使用? 假定對于某個i1, Hi變成了鍵值大于它父節(jié)點鍵值的元素，這樣就違反了堆的特性，因此這種數(shù)據(jù)結(jié)構(gòu)就不再是堆了。如要修復(fù)堆的特性，需要用稱為Sift-up的運算把新的數(shù)據(jù)項上移到在二叉樹中適合它的位置上，這樣堆的屬性就修

6、復(fù)了。 sift-up 運算沿著從Hi到根節(jié)點的惟一一條路徑，把Hi移到適合它的位置上。 在沿著路徑的每一步上，都將Hi鍵值和它父節(jié)點的鍵值Hi/2相比較。QAAlgorithms Design Techniques and Analysis 過程 SIFT-UP輸入:數(shù)組H1n和位于1和n之間的索引i輸出 :上移Hi (如果需要)，以使它不大于父節(jié)點。 1. donefalse 2. if i=1 then exit 節(jié)點i為根 3. repeat 4. if key (Hi)key(H i/2) then 互換 Hi and H i/2 5. else donetrue 6. i i/2

7、7. until i=1 or doneAlgorithms Design Techniques and Analysis 例子310945725112517252025111720EndAlgorithms Design Techniques and AnalysisSift-down 什么時候使用? 假定對于in then exit 節(jié)點 i 是葉子 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 and Ana

8、lysis An example201094537511331135EndAlgorithms Design Techniques and Analysis插入基本思想: 為了把元素x插入到堆H中，先將堆大小加1，然后將x添加到H的末尾，再根據(jù)需要，把x上移，直到滿足堆的特性。算法 4.1 INSERT輸入: 堆H1n 和元素x。輸出: 新的堆 H1n+1 ，x為其元素之一。 1. nn+1 增加H的大小 2. Hnx 3. SIFT-UP(H,n)時間復(fù)雜度：O(logn)Algorithms Design Techniques and Analysis刪除基本思想: 要從大小為n的堆H中刪

9、除元素Hi，可先用Hn替換Hi，然后將堆棧大小減1，如果需要的話，根據(jù)Hi的鍵值與存儲在它父節(jié)點和子節(jié)點中元素鍵值的關(guān)系，對Hi做Sift-up或Sift-down運算，直到滿足堆特性為止。Algorithms Design Techniques and Analysis 算法 4.2 DELETE輸入:非空堆H1n和位于1和n之間的索引i。輸出:刪除Hi之后的新堆H1n-1 。 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-U

10、P(H,i) 6. else SIFT-DOWN(H,i) 7. end if時間復(fù)雜度：O(logn).Algorithms Design Techniques and Analysis刪除最大值基本思想: This這項運算在一個非空堆H中刪除并返回最大鍵值的數(shù)據(jù)項。直接完成這項運算要用到刪除運算:只要返回根節(jié)點中的元素并將其從堆中刪除。算法 4.3 DELETEMAX輸入: 堆H1n.輸出:返回最大鍵值元素x并將其從堆中刪除。1. xH12. DELETE(H,1)3. return x時間復(fù)雜度：O(logn)Algorithms Design Techniques and Analys

11、is4.2.2 創(chuàng)建堆方法1: 給出一個有n個元素的數(shù)組A1.n ，很容易創(chuàng)建一個包含這些元素的堆，可以這樣進(jìn)行:從空的堆開始，不斷插人每一個元素，直到A完全被轉(zhuǎn)移到堆中為止。 將數(shù)組A1.10=4,3,8,10,11,13,7,30,17,26 轉(zhuǎn)換成一個堆.時間復(fù)雜度:因為插人第j個鍵值用時O(logj)，因此用這種方法創(chuàng)建堆棧的時間復(fù)雜性是O(nlogn)。Algorithms Design Techniques and Analysis4.2.2創(chuàng)建堆- contd方法 2: 把一棵n個節(jié)點的幾乎完全的二叉樹轉(zhuǎn)換成堆H1.n。從最后一個節(jié)點開始(編碼為n的那一個)到根節(jié)點(編碼為1的節(jié)

12、點)，逐個掃描所有的節(jié)點，根據(jù)需要，每一次將以當(dāng)前節(jié)點為根節(jié)點的子樹轉(zhuǎn)換成堆。這些元素An/2+1,A n它們對應(yīng)于T的葉子，這樣可以從A n/2開始調(diào)整數(shù)組，并且繼續(xù)An/2-1,A1進(jìn)行調(diào)整。Algorithms Design Techniques and Analysis108 1113730172612345678910將數(shù)組A1.10=4,3,8,10,11,13,7,30,17,26 轉(zhuǎn)換成一個堆. 例子43EndAlgorithms Design Techniques and Analysis算法 4.4 MAKEHEAP 輸入: n個元素的數(shù)組A1n 。輸出: A1n 轉(zhuǎn)換成堆

13、 1. for i n/2 downto 1 2. SIFT-DOWN(A, i) 3. end forAlgorithms Design Techniques and AnalysisMAKEHEAP算法分析設(shè)T是對應(yīng)于數(shù)組A1.n的一棵幾乎完全的二叉樹，那么由觀察結(jié)論3.4可知，T的高是k = logn 。令A(yù)j對應(yīng)該樹的第i層中第j個節(jié)點，當(dāng)語句SIFT-DOWN( A ,j)，調(diào)用過程SiFI-DOWN時，重復(fù)執(zhí)行的次數(shù)最多是k-i因為在第i層上正好有2i個節(jié)點， 0ik ，循環(huán)執(zhí)行的總次數(shù)的上界是:Algorithms Design Techniques and AnalysisMA

14、KEHEAP算法分析由于在過程SIFT-DOWN的每一個循環(huán)中，最多有兩次元素的比較。因此元素比較的總次數(shù)的上界是4n.而且因為在每次調(diào)用過程SIFT-DOWN時，都要至少執(zhí)行一次循環(huán)，元素比較的最小次數(shù)是2n/2n-1. 定理 4.1算法MAKEHEAP用來構(gòu)造一個n元素的堆，令C(n)為執(zhí)行該算法的元素比較次數(shù)，那么n-1 C(n) 4n。時間復(fù)雜度: (n), 空間復(fù)雜度: (1)Algorithms Design Techniques and Analysis4.2.3 堆排序 基本思想給出數(shù)組A1n, 首先將A變換成堆，并使其具有這樣的性質(zhì)，每個元素的鍵值是該元素本身，即key(Ai

15、)=Ai。由于A中各項的最大值存儲在A1中，可以將A1和An交換，使得An是數(shù)組中最大元素。這時，A1中的元素可能小于存放在它的一個子節(jié)點中的元素，于是用過程SIFT-DOWN將A1n-1轉(zhuǎn)換成堆。接下來將A1和An-1交換，并調(diào)整數(shù)組A1n-2成為堆。交換元素和調(diào)整堆的過程一直重復(fù)，直到堆的大小變成i為止，這時，A1是最小的。Algorithms Design Techniques and Analysis 算法 4.5 HEAPSORT輸入: n個元素的數(shù)組A1n 。輸出:以非降序排列的數(shù)組。 1. MAKEHEAP(A) 2. for jn downto 2 3. 互換 A1 and A

16、j 4. SIFT-DOWN(A1j-1,1) 5. end forAlgorithms Design Techniques and Analysis將數(shù)組A1.10=4,3,8,10,11,13,7,30, 17,26 進(jìn)行非降排序 例子108 1113730172612345678910431234567891026438101113730171713 11871034123456789103026123456789104302613171187103Algorithms Design Techniques and AnalysisSort the array A1.10=4,3,8,10

17、,11,13,7,30, 17,26 in non-descending order. An example1713 11871033012345678910426123456789103042613171187103Algorithms Design Techniques and AnalysisSort the array A1.10=4,3,8,10,11,13,7,30, 17,26 in non-descending order. An example1713 118710330123456789104261234567891030426131711871031013 1187433

18、0123456789102617123456789103026171310118743Algorithms Design Techniques and Analysis算法分析空間:這個算法的一個重大好處在于它是在原有的空間里排序，它不需要輔助存儲空間。時間: 建立堆用(n)時間Sift-down運算用O(logj)時間，并且要重復(fù)n一1次， Theorem 4.2 算法HEAPSORT對n個元素排序要用(nlogn)時間和(1)空間。Algorithms Design Techniques and Analysis4.2.4 最小堆和最大堆最大堆: 存儲在根節(jié)點以外的節(jié)點的鍵值，小于或等于存

19、儲在它父節(jié)點中的鍵值。 最小堆:存儲在根節(jié)點以外的節(jié)點的鍵值，大于或等于存儲在它父節(jié)點中的鍵值。 Algorithms Design Techniques and AnalysisA1.10=4,3,8,10,11,13,7,30,17,26 轉(zhuǎn)換成堆. 例子1713 11871034123456789103026Max heap107 111383017261234567891034Min heapAlgorithms Design Techniques and Analysis4.3 不相交集數(shù)據(jù)結(jié)構(gòu)什么是不相交集?假 設(shè)給出一個有n個不同元素的集合S，這些元素被分成不相交集合。在每個子集

20、中，用一個特殊的元素作為集合的名字或代表。 例如，如果集合S=1,2,11有4個子集，分別是1,7,10,11, 2,3,5,6, 4,8 和9, ，這些子集可以依次被標(biāo)記為1,3,8,9。. QAAlgorithms Design Techniques and Analysis不相交集的操作FIND(x): 尋找并返回包含元素x的集合的名字。UNION(x,y):包含元素x和y的兩個集合用它們的并集替換。并集的名字或者是原來包含元素x的那個集合的名字，或者是原來包含元素y的那個集合的名字，這將會在以后確定。 例如，如果集合S=1,2,11有4個子集 1,7,10,11, 2,3,5,6, 4

21、,8 和 9,這些子集可以依次被標(biāo)記為1,3,8,9。FIND(11) 運算返回結(jié)果 1;UNION(1,3) 運算返回新子集被標(biāo)記為1 或 3Algorithms Design Techniques and Analysis 我們的目的是什么?我們的目的是設(shè)計有效算法進(jìn)行FIND和UNION操作。為此需要一種數(shù)據(jù)結(jié)構(gòu)，它既要簡單，同時又要考慮到能有效地實現(xiàn)合并和尋找這兩種運算。How to represent a set?Algorithms Design Techniques and Analysis比特向量表示法 S=1,2,11 and 4 subsets S1=1,7,10,11,

22、S2=2,3,5,6, S3=4,8 and S4=9, S1=10000010011; S2= ; S3= ; S4= 問題: 耗費太多額外資源union操作時間與n相關(guān)，而不是兩個子集的長度Algorithms Design Techniques and AnalysisList 列表表示法The subset is represented as a 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-sort

23、ed 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 sizes of two subsets.Algorithms Design Techniques and AnalysisTree 樹表示法To represent each set as a rooted tree with data eleme

24、nts 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 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)

25、actually means UNION(root(x), root(y).1234567891011Algorithms Design Techniques and Analysis樹的表示法一個子集用一棵樹表示，則所有的不相交子集組成森林。如果假定元素是整數(shù)1,2,n,則森林可以方便地用數(shù)組A1.n來表示，Aj 是元素j的父節(jié)點。空的父節(jié)點可以用數(shù)字0 來表示。1234567891011Algorithms Design Techniques and Analysis 表示法的例子1234567891011030822100111234567891011EndAlgorithms Desi

26、gn Techniques and Analysis直接實現(xiàn)的方法FIND(x): 在進(jìn)行FIND( x )運算時，只是沿著從x開始直到根節(jié)點的路徑，然后返回root(x)。UNION(x,y):在進(jìn)行UNION 運算時，令root(x)的鏈接指向roo(y)，也就是說，如果rooa(x)是u，root(y)是v。，就令v是u的父節(jié)點。Algorithms Design Techniques and AnalysisFIND(X)流程Input: A node x.Output: root(x), the root of the tree containing x.1. yx2. while

27、p(y) null Find the root of the tree containing x3. yp(y)4. end while5. return y;UNION(x,y)流程Input: Two elements 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?考慮以

28、下不相交集合1,2,n 以及操作UNION(1,2), FIND(1), UNION(2,3), FIND(1), UNION(3,4), FIND(1), UNION(4,5),FIND(1), UNION(n-1,n), FIND(1).得到結(jié)果如右所示:nn-11The last find operation requires n times.我們是否能重建沒一棵樹的高度?Algorithms Design Techniques and Analysis4.3.1 按秩合并措施為限制每棵樹的高度，采用按秩合并措施；是使包含較少結(jié)點的樹的根指向包含較多結(jié)點的樹的根，而這個樹的大小可以抽象為

29、樹的高度，即高度小的樹合并到高度大的樹，這樣資源利用更加合理。 基本思想給每個節(jié)點存儲一個非負(fù)數(shù)作為該節(jié)點的秩，記為rank，節(jié)點的秩基本上就是它的高度。設(shè)x和y是當(dāng)前森林中兩棵不同的樹的根初始狀態(tài)時，每個節(jié)點的秩是0在執(zhí)行運算UNION(x, y),時，比較rank(x) 和 rank(y)。如果rank(x)rank(y)，就使得x 為y 的父節(jié)點否則，i如果rank(x)=rank(y)，就使得y 為x 的父節(jié)點，并將 rank(y) 加1。Algorithms Design Techniques and Analysis4.3.1 按秩合并措施為了實現(xiàn)一個按秩合并的不想交集合森林，要記

30、錄下秩的變化。對于每個結(jié)點x，有一個整數(shù)rankx，它是x的高度（從x到其某一個后代葉結(jié)點的最長路徑上邊的數(shù)目）的一個上界。（即樹高）。當(dāng)由MAKE-SET創(chuàng)建了一個單元集時，對應(yīng)的樹中結(jié)點的初始秩為0，每個FIND-SET操作不改變?nèi)魏沃?。?dāng)對兩棵樹應(yīng)用UNION時，有兩種情況，具體取決于根是否有相等的秩。當(dāng)兩個秩不相等時，我們使具有高秩的根成為具有較低秩的根的父結(jié)點，但秩本身保持不變。當(dāng)兩個秩相同時，任選一個根作為父結(jié)點，并增加其秩的值。Algorithms Design Techniques and Analysis 例子n12start213nUNION(1,2)2134nUNION(

31、2,3)2145nUNION(FIND(3),4)32134nUNION(FIND(n-1),n)The result is much better than Straightforward method.Algorithms Design Techniques and Analysis觀察結(jié)論令x是任意節(jié)點，p(x)是x的父節(jié)點，有下面兩個基本的觀察結(jié)論 觀察結(jié)論 4.1rank(p(x) rank(x)+1. 觀察結(jié)論 4.2rank(x)的值初始化為0，在后繼合并運算序列中遞增，直到x不再是根節(jié)點。一旦x變成了其他節(jié)點的一個子節(jié)點，它的秩就不再改變了。 Algorithms Design

32、 Techniques and Analysis 引理引理 4.1 包括根節(jié)點x在內(nèi)的樹中節(jié)點的個數(shù)至少是2rank(x).證明: 對合并運算的次數(shù)應(yīng)用歸納法。最初，x自身形成一棵樹，它的秩為0;設(shè)x和y為兩個根，考慮運算UNION(x,y)。假定引理在這項運算之前成立；如果rank(x)rank(y), 以y（或x）為根形成的樹比老的以y（或x）為根的樹的節(jié)點多，并且它的秩未改變。如果rank(x)rank(y),引理4.1在運算之后成立。如果rank(x)=rank(y),根據(jù)歸納法，在這種情況下，以y為根形成的樹至少有2rank(x) +2rank(y)= 2rank(y)+1個節(jié)點。由

33、于rank (y)每次加1，所以運算之后引理4.1成立。Algorithms Design Techniques and Analysis算法分析每次FIND運算的代價是O(logn).由引理4.1可知，在以x為根的樹中的節(jié)點數(shù)是k，那么樹的高度至多是logk。但在最壞情況下，樹退化成為一條鏈，使得每一次查詢的算法復(fù)雜度為O（N）。運算UNION(x,y)所需要的時間:如果兩個參數(shù)都是根的話，是O(1)。如果x和y不都是根，那么運行時間減少到尋找運算的運行時間。因此，合并運算的時間復(fù)雜性和尋找運算的時間復(fù)雜性相同，都是O (log n)Algorithms Design Techniques

34、and Analysis算法分析 結(jié)論: 可以得出，采用按秩合并措施，m次合并和尋找指令的交替執(zhí)行序列的時間復(fù)雜性是O(m log n)。我們能否進(jìn)一步加強(qiáng)FIND操作的效率？邊查詢邊“路徑壓縮” 其實，我們還能將集合查找的算法復(fù)雜度進(jìn)一步降低：采用“路徑壓縮”算法。它的想法很簡單：在集合的查找過程中順便將樹的深度降低。采用路徑壓縮后，每一次查詢所用的時間復(fù)雜度為增長極為緩慢的阿克曼函數(shù)（ackerman函數(shù)）的反函數(shù)（x）。對于可以想象到的n，（n）都是在5之內(nèi)的。返回Algorithms Design Techniques and Analysis4.3.2 路徑壓縮在FIND(x) 運算

35、中，找到根節(jié)點y之后，我們再一次遍歷從x到y(tǒng)的路徑，并沿著路徑改變所有節(jié)點指向父節(jié)點的指針，使它們直接指向y。Algorithms Design Techniques and Analysis 例子12341432執(zhí)行帶有路徑壓縮的尋找運算F7ND(4)的效果元素的合并圖示13245合并1和2合并1和3合并5和4合并5和3路徑壓縮示意圖13245由此我們得到了一個復(fù)雜度只是O(1)的算法Algorithms Design Techniques and Analysis4.3.3 union-find 算法（路徑壓縮）算法 4.6 FIND輸入: 節(jié)點x.輸出: root(x),包含x的樹的根。

36、 1. yx 2. while p(y) null 尋找包含x的樹的根 3. yp(y) 4. end while 5. rooty; yx 6. while p(y) null 執(zhí)行路徑壓縮 7. wp(y); p(y)root; yw 8. end while 9. return rootAlgorithms Design Techniques and Analysis算法 4.7 UNIONInput:兩個元素x和yOutput:包含x和y的兩個樹的合并，原來的樹被破壞。1. 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 union-find算法（按秩合并）Algorithms Design Techniques and Analysis 例子設(shè)S=1,2,9，考慮用下面的合并和尋找序列：