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

算法設(shè)計與分析

AlgorithmsDesignandAnalysis

趙廷剛蘭州城市學(xué)院數(shù)學(xué)學(xué)院2013.3本章內(nèi)容4.1引言4.2堆(heaps)4.2.1堆上的運算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)是計算機中存儲、組織數(shù)據(jù)的方式。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來最優(yōu)效率的算法。

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