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

算法設(shè)計(jì)與分析

AlgorithmsDesignandAnalysis

趙廷剛蘭州城市學(xué)院數(shù)學(xué)學(xué)院2013.3本章內(nèi)容4.1引言4.2堆(heaps)4.2.1堆上的運(yùn)算4.2.2創(chuàng)建堆4.2.3堆排序4.2.4最小堆和最大堆4.3不相交集數(shù)據(jù)結(jié)構(gòu)(disjointsetsdatastructures)4.3.1按秩合并措施4.3.2路徑壓縮4.3.3UNION-FIND算法4.3.4UNION-FIND算法分析

數(shù)據(jù)結(jié)構(gòu)(datastructure)是計(jì)算機(jī)中存儲(chǔ)、組織數(shù)據(jù)的方式。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)最優(yōu)效率的算法。

4.1引言常見(jiàn)數(shù)據(jù)結(jié)構(gòu)：數(shù)組(array)、列表(list)、堆棧(stack)、隊(duì)列(queue)、鏈表(linkedlist)、樹(shù)(tree)、圖(graph)、堆(heap)、散列(hash)4.2堆（heaps）在許多算法中，需要支持兩種運(yùn)算的數(shù)據(jù)結(jié)構(gòu)：插入元素和尋找最大值元素。支持這兩種運(yùn)算的數(shù)據(jù)結(jié)構(gòu)稱為優(yōu)先隊(duì)列。如果使用普通隊(duì)列，那么尋找最大元素需要搜索整個(gè)隊(duì)列，開(kāi)銷比較大；如果采用排序數(shù)組，那么插入運(yùn)算就需要移動(dòng)很多元素，開(kāi)銷也會(huì)較大。優(yōu)先隊(duì)列的有效實(shí)現(xiàn)是使用“堆”的簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)。一個(gè)（二叉）堆是一個(gè)幾乎完全的二叉樹(shù)，它的每個(gè)節(jié)點(diǎn)都滿足堆的特性：如果v和p(v)分別是節(jié)點(diǎn)和它的父節(jié)點(diǎn)，那么存儲(chǔ)在p(v)中的數(shù)據(jù)項(xiàng)鍵值不小于存儲(chǔ)在v中的數(shù)據(jù)項(xiàng)鍵值。定義4.1堆數(shù)據(jù)結(jié)構(gòu)支持下面的運(yùn)算：delete-max[H]:從堆H中刪除最大鍵值的數(shù)據(jù)項(xiàng)并將數(shù)據(jù)項(xiàng)返回。insert[H,x]:插入項(xiàng)x到堆H中。delete[H,i]:從堆H中刪除第i項(xiàng)。makeheap[A]:將數(shù)組A轉(zhuǎn)換成堆。堆的例子/view/4147d863caaedd3383c4d3c6.html注意：如果堆中的節(jié)點(diǎn)有右子節(jié)點(diǎn)，則它一定也有左子節(jié)點(diǎn)。堆可以看做是二叉樹(shù)，而它實(shí)質(zhì)上是一個(gè)數(shù)組H[1…n]。它有如下性質(zhì)：/p-240830965233.html4.2.1堆上的運(yùn)算----sift-up假設(shè)對(duì)某個(gè)i>1,H[i]變成了鍵值大于它的父節(jié)點(diǎn)鍵值的元素，這樣就違反了堆性質(zhì)，因此該數(shù)據(jù)結(jié)構(gòu)就不再是堆了，如果要修復(fù)它成為堆，就用sift-up的運(yùn)算.算法描述：Sift-up運(yùn)算沿著從H[i]到根節(jié)點(diǎn)的唯一一條路徑，把H[i]移到適合它的位置上。在沿著路徑的每一步上，都將H[i]鍵值與它的父節(jié)點(diǎn)的鍵值相比較。4.2.1堆上的運(yùn)算----sift-down假設(shè)對(duì)i≤floor(i/2),存儲(chǔ)在H[i]中元素的鍵值變成小于H[2i]和H[2i+1]中的最大值，這樣也違反了堆性質(zhì)，因此該數(shù)據(jù)結(jié)構(gòu)就不再是堆了，如果要修復(fù)它成為堆，就用sift-down的運(yùn)算.算法描述：Sift-down運(yùn)算使H[i]“滲”到二叉樹(shù)中適合它的位置上，沿著路徑的每一步上，都將H[i]鍵值與存儲(chǔ)在它的子節(jié)點(diǎn)（如果有）的兩個(gè)（可能是一個(gè)）鍵值里最大的那個(gè)相比較。4.2.1堆上的運(yùn)算----插入（insert）插入：為了把元素x插入到堆H中，先將堆大小加1，然后將x添加到H的末尾，再根據(jù)需要，將x上移，直到滿足堆性質(zhì).4.2.1堆上的運(yùn)算----刪除（delete）刪除：要從大小為n的堆H中刪除元素H[i]，可先用H[n]替換H[i],然后將堆棧大小減1，如果需要的話，根據(jù)H[i]的鍵值與存儲(chǔ)在它的父節(jié)點(diǎn)和子節(jié)點(diǎn)中元素鍵值的大小，對(duì)H[i]做sift-up或sift-down運(yùn)算，直到滿足堆性質(zhì).4.2.1堆上的運(yùn)算----刪除最大值（delete-max）刪除最大值：要從大小為n的堆H中刪除元素H[i]，可先用H[n]替換H[i],然后將堆棧大小減1，如果需要的話，根據(jù)H[i]的鍵值與存儲(chǔ)在它的父節(jié)點(diǎn)和子節(jié)點(diǎn)中元素鍵值的大小，對(duì)H[i]做sift-up或sift-down運(yùn)算，直到滿足堆性質(zhì).4.2.2堆上的運(yùn)算----創(chuàng)建堆（makeheap）創(chuàng)建堆：給出一個(gè)有n個(gè)元素的數(shù)組A[1…n]，將該數(shù)組變成一個(gè)幾乎完全的二叉樹(shù)，并把這個(gè)二叉樹(shù)轉(zhuǎn)換成一個(gè)堆。從最后一個(gè)節(jié)點(diǎn)開(kāi)始(編碼為n的節(jié)點(diǎn))到根節(jié)點(diǎn)(編碼為1的節(jié)點(diǎn))，逐個(gè)掃描，根據(jù)需要每次將當(dāng)前節(jié)點(diǎn)為根的子樹(shù)轉(zhuǎn)換為堆。例4.34.2.3堆排序算法描述：給出數(shù)組A[1…n]，首先將它轉(zhuǎn)換為堆，由于最大值在A[1]中，所以將A[1]和A[n]互換，這樣A[n]中存放了最大值，接下來(lái)考慮數(shù)組A[1…n-1]，它可能不是堆，利用sift-down運(yùn)算將A[1…n-1]轉(zhuǎn)換成堆，再將A[1]和A[n-1]互換，如此下去，直到堆的大小變?yōu)?，即可。4.3不相交集數(shù)據(jù)結(jié)構(gòu)假設(shè)有一個(gè)包含n個(gè)元素的集合S,它被分成不相交的一些子集，每個(gè)子集用其中的一個(gè)元素做名字或代表。例如：S={1,2,……,11},子集合為{1,7,10,11},{2,3,5,6},{4,8},{9}這4個(gè)子集合被依次命名為1,3,8,9.FIND(x):返回包含x的子集合的名字。UNION(x,y)：將包含x的子集合與包含y的子集合合并，得到的并集的名字取原來(lái)兩個(gè)子集合的名字之一。根樹(shù)表示法：用根樹(shù)表示每個(gè)子集合，子集合中的元素存儲(chǔ)在節(jié)點(diǎn)中，樹(shù)中除根節(jié)點(diǎn)外的每一個(gè)元素x都有一個(gè)指向父節(jié)點(diǎn)p(x)的指針.根有一個(gè)空指針，用作集合的名字或代表。這些根樹(shù)在一起組成一個(gè)森林。對(duì)于任意元素x，用root(x)表示包含x的樹(shù)的根。那么，F(xiàn)IND(x)總是返回root(x)。由于合并運(yùn)算必須有兩棵樹(shù)的根作為它的參數(shù)，我們將假定對(duì)于任意兩個(gè)元素x和y,UNION(x,y)實(shí)際上是表示UNION(root(x),root(y)).在進(jìn)行FIND(x)運(yùn)算時(shí)，只是沿著從x開(kāi)始直到根節(jié)點(diǎn)的路徑，然后返回root(x)。在進(jìn)行UNION(x,y)運(yùn)算時(shí)，令root(x)的鏈接指向root(y)，也就是說(shuō)，如果root(x)是u，root(y)是v,就令v是u的父節(jié)點(diǎn).一個(gè)極端例子：假設(shè)集合S={1,2,…,n}，它的子集合為：{1},{2},…,{n}.執(zhí)行n-1個(gè)合并運(yùn)算：UNION{1,2},UNION{2,3},…,UNION{n-1,n}之后的結(jié)果見(jiàn)圖4.6(a)，這是一個(gè)高度為n-1的樹(shù)。如果接下來(lái)要執(zhí)行尋找運(yùn)算：FIND(1),FIND(2),…,FIND(n),則n次尋找的總代價(jià)為：這是很耗費(fèi)時(shí)間的，為了克服這個(gè)弊端，采用：按秩合并措施和路徑壓縮措施。4.3.1按秩合并措施為了限制每棵樹(shù)的高度，采用按秩合并措施：給每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)非負(fù)數(shù)作為該節(jié)點(diǎn)的秩，記為rank,節(jié)點(diǎn)的秩基本上就是它的高度。設(shè)x和y是當(dāng)前森林中兩棵不同的根樹(shù)的根，初始狀態(tài)時(shí)，每個(gè)節(jié)點(diǎn)的秩是0，在執(zhí)行運(yùn)算UNION(x,y)時(shí)，比較rank(x)和rank(y),如果rank(x)<rank(y),就使y為x的父節(jié)點(diǎn)；如果rank(x)>rank(y),就使x為y的父節(jié)點(diǎn)；如果rank(x)=rank(y),就使y為x的父節(jié)點(diǎn),并rank(y)加1.那個(gè)極端例子：按照上述規(guī)則之后的結(jié)果見(jiàn)圖4.6(b)，這是一個(gè)高度為1的樹(shù)。如果接下來(lái)要執(zhí)行尋找運(yùn)算：FIND(1),FIND(2),…,FIND(n),則n次尋找的總代價(jià)為：n