第四章堆和不相交集數(shù)據(jù)結(jié)構(gòu)

1、蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 算法設(shè)計與分析算法設(shè)計與分析 Algorithms Design and Analysis 趙廷剛 蘭州城市學(xué)院數(shù)學(xué)學(xué)院蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 本章內(nèi)容4.1 引言引言4.2 堆堆(heaps)4.2.1 堆上的運算4.2.2 創(chuàng)建堆4.2.3 堆

2、排序4.2.4 最小堆和最大堆4.3 不相交集數(shù)據(jù)結(jié)構(gòu)不相交集數(shù)據(jù)結(jié)構(gòu)(disjoint sets data structures)4.3.1 按秩合并措施4.3.2 路徑壓縮4.3.3 UNION-FIND算法4.3.4 UNION-FIND算法分析蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)( (data structure) )是計算機(jī)中存儲、組織數(shù)據(jù)的方式。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來最優(yōu)效率的算法。 4.1 引言常見

3、數(shù)據(jù)結(jié)構(gòu)：數(shù)組常見數(shù)據(jù)結(jié)構(gòu)：數(shù)組( (array) )、列表、列表( (list) )、堆棧、堆棧( (stack) )、隊列隊列( (queue) )、鏈表、鏈表( (linked list) )、樹、樹( (tree) )、圖、圖( (graph) )、堆堆( (heap) )、散列、散列( (hash) )蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 4.2 4.2 堆（堆（heaps）在許多算法中，需要支持兩種運算的數(shù)據(jù)結(jié)構(gòu)：插入元素和尋找最大在

4、許多算法中，需要支持兩種運算的數(shù)據(jù)結(jié)構(gòu)：插入元素和尋找最大值元素。支持這兩種運算的數(shù)據(jù)結(jié)構(gòu)稱為值元素。支持這兩種運算的數(shù)據(jù)結(jié)構(gòu)稱為優(yōu)先隊列優(yōu)先隊列。如果使用普通隊。如果使用普通隊列，那么尋找最大元素需要搜索整個隊列，開銷比較大；如果采用排列，那么尋找最大元素需要搜索整個隊列，開銷比較大；如果采用排序數(shù)組，那么插入運算就需要移動很多元素，開銷也會較大。優(yōu)先隊序數(shù)組，那么插入運算就需要移動很多元素，開銷也會較大。優(yōu)先隊列的有效實現(xiàn)是使用列的有效實現(xiàn)是使用“堆堆”的簡單數(shù)據(jù)結(jié)構(gòu)。的簡單數(shù)據(jù)結(jié)構(gòu)。 一個（二叉）堆是一個幾乎完全的二叉樹，它的每個節(jié)點都一個（二叉）堆是一個幾乎完全的二叉樹，它的每個節(jié)點都

5、滿足堆的特性：如果滿足堆的特性：如果v和和p(v)分別是節(jié)點和它的父節(jié)點，那么存儲分別是節(jié)點和它的父節(jié)點，那么存儲在在p(v)中的數(shù)據(jù)項鍵值不小于存儲在中的數(shù)據(jù)項鍵值不小于存儲在v中的數(shù)據(jù)項鍵值。中的數(shù)據(jù)項鍵值。定義定義4.1 堆數(shù)據(jù)結(jié)構(gòu)支持下面的運算： delete-maxH:從堆從堆H中刪除最大鍵值的數(shù)據(jù)項并將數(shù)據(jù)項返回中刪除最大鍵值的數(shù)據(jù)項并將數(shù)據(jù)項返回。 insertH,x:插入項插入項x到堆到堆H中。中。 deleteH,i:從堆從堆H中刪除第中刪除第i項。項。 makeheapA:將數(shù)組將數(shù)組A轉(zhuǎn)換成堆。轉(zhuǎn)換成堆。蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分

6、析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 堆的例子蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) http:/ 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) http:/ 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techn

7、iques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 4.2.1 堆上的運算-sift-up假設(shè)對某個假設(shè)對某個i1,Hii1,Hi變成了鍵值大于它的父節(jié)點鍵值的元變成了鍵值大于它的父節(jié)點鍵值的元素，這樣就違反了堆性質(zhì)，因此該數(shù)據(jù)結(jié)構(gòu)就不再是堆了，素，這樣就違反了堆性質(zhì)，因此該數(shù)據(jù)結(jié)構(gòu)就不再是堆了，如果要修復(fù)它成為堆，就用如果要修復(fù)它成為堆，就用sift-upsift-up的運算的運算. 蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 算法描

8、述：Sift-up運算沿著從Hi到根節(jié)點的唯一一條路徑，把Hi移到適合它的位置上。在沿著路徑的每一步上，都將Hi鍵值與它的父節(jié)點的鍵值 相比較。蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 4.2.1 堆上的運算-sift-down假設(shè)對假設(shè)對ifloor(i/2),i

9、floor(i/2),存儲在存儲在HiHi 中元素的鍵值變成小于中元素的鍵值變成小于H2iH2i和和H2i+1H2i+1中的最大值，這樣也違反了堆性質(zhì)，因此中的最大值，這樣也違反了堆性質(zhì)，因此該數(shù)據(jù)結(jié)構(gòu)就不再是堆了，如果要修復(fù)它成為堆，就用該數(shù)據(jù)結(jié)構(gòu)就不再是堆了，如果要修復(fù)它成為堆，就用sift-downsift-down的運算的運算. 蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 算法描述：Sift-down運算使Hi“滲”到二叉樹中適合它的位置上，沿

10、著路徑的每一步上，都將Hi鍵值與存儲在它的子節(jié)點（如果有）的兩個（可能是一個）鍵值里最大的那個相比較。蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 4.2.1 堆上的運算-插入（insert）插入：為了把元素插入：為了把元素x x插入到堆插入到堆H H中，先將堆大小加中

11、，先將堆大小加1 1，然后，然后將將x x添加到添加到H H的末尾，再根據(jù)需要，將的末尾，再根據(jù)需要，將x x上移，直到滿足堆上移，直到滿足堆性質(zhì)性質(zhì). 蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 4.2.1 堆上的運算-刪除（delete）刪除：要從大小為刪除：要從大小為n n的堆的堆H H中刪除元素中刪除元素HiHi ，可先用，可先用HnHn 替替換換HiHi,然后將堆棧大小減然后將堆棧大小減1 1，如果需要的話，根據(jù)，如果需要的話，根據(jù)HiHi

12、的的鍵值與存儲在它的父節(jié)點和子節(jié)點中元素鍵值的大小，對鍵值與存儲在它的父節(jié)點和子節(jié)點中元素鍵值的大小，對HiHi 做做sift-upsift-up或或sift-downsift-down運算，直到滿足堆性質(zhì)運算，直到滿足堆性質(zhì). 蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 4.2.1 堆上的運算-刪除最大值（delete-max）刪除最大值：要從大小為刪除最大值：要從大小為n n的堆的堆H H中刪除元素中刪除元素HiHi ，可先用，可先用HnHn 替換

13、替換HiHi,然后將堆棧大小減然后將堆棧大小減1 1，如果需要的話，根據(jù)，如果需要的話，根據(jù)HiHi 的鍵值與存儲在它的父節(jié)點和子節(jié)點中元素鍵值的大的鍵值與存儲在它的父節(jié)點和子節(jié)點中元素鍵值的大小，對小，對HiHi 做做sift-upsift-up或或sift-downsift-down運算，直到滿足堆性質(zhì)運算，直到滿足堆性質(zhì). 蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 4.2.2 堆上的運算-創(chuàng)建堆（make heap）創(chuàng)建堆：給出一個有創(chuàng)建堆：給

14、出一個有n n個元素的數(shù)組個元素的數(shù)組A1A1nn，將該數(shù)組變，將該數(shù)組變成一個幾乎完全的二叉樹，并把這個二叉樹轉(zhuǎn)換成一個堆。成一個幾乎完全的二叉樹，并把這個二叉樹轉(zhuǎn)換成一個堆。從最后一個節(jié)點開始從最后一個節(jié)點開始( (編碼為編碼為n n的節(jié)點的節(jié)點) )到根節(jié)點到根節(jié)點( (編碼為編碼為1 1的節(jié)點的節(jié)點) )，逐個掃描，根據(jù)需要每次將當(dāng)前節(jié)點為根的子，逐個掃描，根據(jù)需要每次將當(dāng)前節(jié)點為根的子樹轉(zhuǎn)換為堆。樹轉(zhuǎn)換為堆。蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集

15、數(shù)據(jù)結(jié)構(gòu) 例例蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 4.2.3 堆排序算法描述：給出數(shù)組A1n，首先將它轉(zhuǎn)換為堆，由于最大值在A1中，所以將A1和An互換，這樣An中存放了最大值，接下來考慮數(shù)組A1n-1，它可能不是堆，利用sift-down運算將A1n-1轉(zhuǎn)換

16、成堆，再將A1和An-1互換，如此下去，直到堆的大小變?yōu)?，即可。蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 4.3 不相交集數(shù)據(jù)結(jié)構(gòu)假設(shè)有一個包含n個元素的集合S,它被分成不相交的一些子集，每個子集用其中的一個元素做名字或代表。例如：S=1,2,11, 子集合為1,

17、7,10,11, 2,3,5,6, 4,8, 9 這4個子集合被依次命名為1,3,8,9. FIND(x): 返回包含x的子集合的名字。 UNION(x,y)：將包含x的子集合與包含y的子集合合并，得到的并集的名字取原來兩個子集合的名字之一。蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 根樹表示法根樹表示法：用根樹表示每個子集合，子集合中的元素存儲在節(jié)點中，用根樹表示每個子集合，子集合中的元素存儲在節(jié)點中，樹中除根節(jié)點外的每一個元素樹中除根節(jié)點外的每一個

18、元素x都有一個指向父節(jié)點都有一個指向父節(jié)點p(x)的指針的指針.根有一根有一個空指針，用作集合的名字或代表。這些根樹在一起組成一個森林。個空指針，用作集合的名字或代表。這些根樹在一起組成一個森林。 對于任意元素對于任意元素x，用，用root(x)表示包表示包含含x的樹的根的樹的根。那么，那么，F(xiàn)IND(x)總是返回總是返回root(x)。由于合并運算必須有兩棵樹的。由于合并運算必須有兩棵樹的根作為它的參數(shù)，我們將假定對于任意根作為它的參數(shù)，我們將假定對于任意兩個元素兩個元素x和和y,UNION(x,y)實際上是表實際上是表示示UNION(root(x),root(y). 在進(jìn)行在進(jìn)行FIND(

19、x)運算時，只是沿著運算時，只是沿著從從x開始直到根節(jié)點的路徑，然后返回開始直到根節(jié)點的路徑，然后返回root(x)。 在進(jìn)行在進(jìn)行UNION(x,y)運算時，令運算時，令root(x)的鏈接指向的鏈接指向root(y)，也就是說，也就是說，如果如果root(x)是是u，root(y)是是v,就令就令v是是u的父節(jié)點的父節(jié)點蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 一個極端例子一個極端例子：假設(shè)集合S=1,2,n，它的子集合為：1,2,n. 執(zhí)行n-

20、1個合并運算：UNION1,2,UNION2,3,UNIONn-1,n 之后的結(jié)果見圖4.6(a)，這是一個高度為n-1的樹。如果接下來要執(zhí)行尋找運算：FIND(1),FIND(2),FIND(n),則n次尋找的總代價為：這是很耗費時間的，為了克服這個弊端，采用：按秩合并措施按秩合并措施和路徑壓縮措施路徑壓縮措施。蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 4.3.1 4.3.1 按秩合并措施按秩合并措施 為了限制每棵樹的高度，采用按秩合并措施為了限制

21、每棵樹的高度，采用按秩合并措施：給每個節(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é)點；如果rank(x)=rank(y),就使y為x的父節(jié)點,并rank(y)加1. 那個極端例子那個極端例子：按照上述規(guī)則之后的結(jié)果見圖4.6(b)，這是一個高度為1的樹。如果接下來要執(zhí)行尋找運算：FIND(1),FIND(2),FIND(n),則n次尋找的總代價為：蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 Algorithms Design Techniques and Analysis 第四章 堆和不相交集數(shù)據(jù)結(jié)構(gòu) 一些結(jié)論一些結(jié)論蘭州城市學(xué)院數(shù)學(xué)學(xué)院算算 法法 設(shè)設(shè) 計計 技技 巧巧 與與 分分 析析 A