算法設計與分析

AlgorithmsDesignandAnalysis

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

數據結構(datastructure)是計算機中存儲、組織數據的方式。通常情況下，精心選擇的數據結構可以帶來最優效率的算法。

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