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

第四章堆和不相交集數(shù)據(jù)結(jié)構(gòu)4.1引言4.2堆4.3不相交集數(shù)據(jù)結(jié)構(gòu)14.2堆

在許多算法中，需要支持下面兩種運算的數(shù)據(jù)結(jié)構(gòu)：

插入元素和尋找最大元素。支持這兩種運算的數(shù)據(jù)結(jié)構(gòu)稱為優(yōu)先隊列。普通隊列:那么尋找最大元素需要搜索整個隊列，開銷較大；2排序數(shù)組:那么插入運算就需要移動很多元素，開銷也較大.優(yōu)先隊列的有效實現(xiàn)是使用一種稱為堆的簡單數(shù)據(jù)結(jié)構(gòu)。3定義4.1

一個（二叉）堆是一個幾乎完全的二叉樹，它的每個節(jié)點都滿足堆的特性：如果v和p(v)分別是節(jié)點和它的父節(jié)點，那么存儲在p(v)中的數(shù)據(jù)項鍵值不小于存儲在v中數(shù)據(jù)項的鍵值。（大頂堆）4堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或數(shù)據(jù)結(jié)構(gòu)中堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小頂堆)(大頂堆)5rir2ir2i+1

若將該數(shù)列視作完全二叉樹，則r2i

是ri

的左孩子;r2i+1

是ri

的右孩子。1236276549817355403498例如:是堆6對數(shù)據(jù)結(jié)構(gòu)支持下面的運算：Delete-max[H]：刪除最大鍵值的數(shù)據(jù)項Insert[H,x]：插入項x到堆H中Delete[H,i]：從堆H中刪除第i項Makeheap[A]：將數(shù)組A轉(zhuǎn)換成堆

堆的特性蘊含著：沿著每條從根到葉子的路徑，元素的鍵值以非升序排列。（大頂堆）7有n個節(jié)點的堆T（一棵幾乎完全的二叉樹），可以有一個數(shù)組H[1…n]用下面的方式來表示。

T的根節(jié)點存儲在H[1]中。假設(shè)T的節(jié)點x存儲在H[j]中，如果它有左子節(jié)點，這個子節(jié)點存儲在H[2j]中；如果它也有右子節(jié)點，這個子節(jié)點存儲在H[2j+1]中。8元素H[j]的父節(jié)點如果不是根節(jié)點，則存儲在H[

j/2

]中。94.2.1堆上的運算下面是兩個輔助運算Sift-up

運算

:

前提：假定對于某個i>1,H[i]變成了鍵值大于它父節(jié)點鍵值的元素，非堆結(jié)構(gòu)。

處理方案：調(diào)整破壞堆的數(shù)據(jù)的位置；

實際方法：沿著從H[i]的根節(jié)點的唯一一條路經(jīng)，把H[i]移到適合它的位置上。在沿著路徑的每一步上，都將H[i]鍵值和它父節(jié)點的鍵值H[i/2

]相比較。10過程：Sift-up算法輸入：數(shù)組H[1…n]和位于1和n之間的索引i輸出：上移H[i]，以使它不大于父節(jié)點1.done

false2.ifi=1thenexit//節(jié)點i是根

3.repeat4.ifkey(H[i])>key(H[i/2])then互換H[i]和H[i/2]//對比交換5.Elsedone

true6.ii/2

7.Untili=1ordone11Sift-down

算法：

前提：當(dāng)i≤n/2,

設(shè)H[2i]和H[2i+1]中最大值為max，如果H[i]中元素的鍵值變成了小于max，這樣就違反了堆的特性，樹就不再表示一個堆。調(diào)整策略：使H[i]滲到二叉樹中適合它的位置上；

沿著這條路徑的每一步，都將H[i]鍵值和存儲在它子節(jié)點中的兩個鍵值里最大的那個相比較。12過程：Sift-down輸入：數(shù)組H[1…n]和位于1和n之間的索引i輸出：下移H[i]，以使它不小于子節(jié)點1.done

false2.if2i>nthenexit

//節(jié)點i是葉子，退出

3.repeat4.i=2i

//待比較位置左子節(jié)點

5.ifi+1≤nandkey(H[i+1])>key(H[i])thenii+1

//存在右子節(jié)點，且右子節(jié)點最大

6.ifkey(H[i/2])<key(H[i])//與最大節(jié)點交換

then互換H[i]和H[i/2]

7.Elsedone

true8.Endif9.Until2i>nordone13算法復(fù)雜度分析Sift_down的復(fù)雜度分析：（1）以i結(jié)點和2i+1,2i+2的調(diào)整復(fù)雜度所用時間為（2）以2i+1或2i+2結(jié)點為父結(jié)點來調(diào)整的時間最壞是多少？發(fā)生調(diào)整的幾率的樹最多是2n/3，（即最底層恰好是半滿）。則：，根據(jù)遞推式求解：O(logn)14算法4.1INSERT輸入：堆H[1…n]和元素x輸出：新的堆H[1…n+1]，x為其元素之一

1.n=n+1{增加H的大小}2.H[n]x

3.SIFT-UP(H,n)15插入

（1）先將堆大小加1，然后將x添加到H的末尾，再根據(jù)需要，把x上移，直到滿足堆特性，（2）觀察結(jié)論3.4可知，如果n是新堆的大小，那么堆樹的高度是logn，所以將一個元素插入大小為n的堆中所需要的時間是O(log

n)。16算法4.2DELETE//刪除某個元素輸入：非空堆H[1…n]和位于1和n之間的索引i輸出：刪除H[i]后的新堆H[1…n-1]1.x

H[i];y

H[n]

//刪除x，最后一個數(shù)據(jù)暫存y2.n=n-1//數(shù)組大小減13.Ifi=n+1thenexit

//刪除的元素正好是最后一個，不需要任何操作4.H[i]y;//不是最后一個則取回最后一個，先放入H[i]中

5.If

key(y)≥key(x)thenSIFT-UP(H,i)6.

ElseSIFT-DOWN(H,i)

//根據(jù)需要進行調(diào)整

7.ENDIF17刪除復(fù)雜度：這些在算法DELETE中描述。有觀察結(jié)論3.4可知，堆樹的高度是logn，所以從一個大小為n的堆中刪除一個元素所需要的時間是O(log

n)。18算法4.3DELETEMAX//刪除根節(jié)點輸入：堆H[1…n]輸出：返回最大值元素

x并將其從堆中刪除

1.x

H[1]2.DELETE(H,1)

3.Returnx19刪除最大值復(fù)雜度分析：（1）在堆中返回最大鍵值元素需要Θ(1)的時間，因為這個元素是樹的根節(jié)點。(2)修復(fù)堆需要一定的時間。顯然，這項運算的時間復(fù)雜性就是刪除運算的時間復(fù)雜性，即O(log

n)。204.2.2創(chuàng)建堆

給出一個A[1…n]，創(chuàng)建一個包含這些元素的堆是容易的：從空的堆開始，不斷插入一個元素，直到A完全被轉(zhuǎn)移到堆中為止。因為插入第j個鍵值用時O(log

j)，因此用此方法創(chuàng)建堆棧的時間復(fù)雜性是O(n

logn)。

21看另外一個堆建立方法：在Θ(n)的時間內(nèi)，用n個元素來建立一個堆，下面給出這種方法的實現(xiàn)細(xì)節(jié)。22(1)將堆H[1…n]的樹的節(jié)點以自頂向下、從左到右的方式從1到n編碼。(2)把一棵n個節(jié)點的幾乎完全的二叉樹轉(zhuǎn)換成堆H[1…n]。(3)從最后一個節(jié)點開始（編碼為n的那個）到根節(jié)點（編碼為1的節(jié)點），逐個掃描所有的節(jié)點，根據(jù)需要，每一次將以當(dāng)前節(jié)點為根節(jié)點的子樹轉(zhuǎn)換成堆。見例4.3創(chuàng)建堆的例子(手寫)23算法MAKEHEAP構(gòu)建了一個堆，其數(shù)據(jù)項是存儲在數(shù)組A[1…n]中的元素。算法4.4MAKEHEAP輸入：n個元素的數(shù)組A[1…n]輸出：A[1…n]轉(zhuǎn)換成堆1.Fori

n/2downto12.SIFT-DOWN(A,i)3.Endfor

//注：葉子節(jié)點不需要處理，所以必須從n/2開始處理，A[n/2+1]，A[n/2+2],..A[n]對應(yīng)于數(shù)的葉子節(jié)點24算法復(fù)雜度分析：

(1)設(shè)T是一個完全二叉樹，高度是k=logn。(2)設(shè)A[j]對應(yīng)第i層的第j個結(jié)點，則調(diào)用sift-down函數(shù)需要調(diào)用的次數(shù)應(yīng)該最多是k-i(注：k是樹的高度)（自底而上掃描連接的數(shù)據(jù)）。(3)根據(jù)二叉樹的理論知：二叉樹的第i層最多有2i個結(jié)點，則循環(huán)的上界應(yīng)該為：

25定理4.1算法MAKEHEAP用來構(gòu)造一個n個元素的堆，令C(n)為執(zhí)行該算法的元素比較次數(shù)，那么n-1≤C(n)＜4n。因此，算法需要Θ(n)時間和Θ(1)空間構(gòu)造一個n元素的堆。

觀察sift-down函數(shù)，每一次循環(huán)過程，包含有兩個if語句，故最多兩次元素比較，故元素比較的總次數(shù)上界是2*2n=4n；觀察下界：調(diào)用sift-down函數(shù)至少要執(zhí)行一次循環(huán)，所以元素的最小比較次數(shù)應(yīng)為:2*n/2>=n-1。26另外一種分析方法：1、簡單的分析：每次調(diào)用SIFT-DOWN()函數(shù)的時間為O(logn)，一共應(yīng)該有n/2次調(diào)用，所以總的時間復(fù)雜度上線是O(nlogn)。但是這個上限太高了。（這就意味著幾乎每一個結(jié)點都在執(zhí)行sift_down()函數(shù)行為）27分析一個確界：1、事實上，需要執(zhí)行SIFT-DOWN()函數(shù)的結(jié)點很少，而且對于不同的節(jié)點執(zhí)行SIFT-DOWN()函數(shù)的次數(shù)也是不同的，這跟每一個結(jié)點所處的高度和所連接的數(shù)據(jù)相關(guān)。28一個n元素的堆的高度是，在任意的高度h上，最多有結(jié)點數(shù)設(shè)SIFT-DOWN()在h層上的作用時間是O(h)，則應(yīng)該有一個上確界：（1）29數(shù)論上存在如下等式成立：設(shè)x=1/2帶入（1）的右邊的和式304.2.3堆排序

算法SELECTIONSORT(選擇排序)的復(fù)雜度：

用線性搜索來找最小值的時間需要用Θ(n)的時間，算法就要用Θ(n2)時間。如何提高選擇排序的復(fù)雜度呢，使用堆是一個好的選擇。31給出數(shù)組A[1…n]，將其中的元素用如下方法以非降序有效排序。

step1.首先將A變換成堆，并使其具有這樣的性質(zhì)，每個元素的鍵值是該元素本身，即key(A[i])=A[i],1≤i≤n。32

step2.由于A中各項的最大值存儲在A[1]中，可以將A[1]和A[n]交換，使得A[n]是數(shù)組中最大元素。

(排序：將數(shù)據(jù)依大小，順序放在數(shù)組中，最后一個是最大的，故交換A[1]和A[n])33這時，A[1]中的元素可能小于存放在它的一個子節(jié)點中的元素，于是用過程SIFT-DOWN將A[1…n-1]轉(zhuǎn)換成堆。(調(diào)整堆)接下來將A[1]和A[n-1]交換，并調(diào)整數(shù)組A[1…n-2]成為堆。交換元素和調(diào)整堆的過程一直重復(fù)，直到堆的大小變成1為止，這時A[1]是最小的。34算法4.5HEAPSORT輸入：n個元素的數(shù)組A[1…n]輸出：以非降序排列的數(shù)組A1.MAKEHEAP(A)2.forjndownto2//j從n依次遞減

3.互換A[1]A[j]4.SIFT-DOWN(A[1…j-1],1)5.endfor定理4.2算法HEAPSORT對n個元素排序要用O(n

logn)時間和Θ(1)的空間。354.2.4最小堆和最大堆到現(xiàn)在為止，我們把堆看作是一個數(shù)據(jù)結(jié)構(gòu)，它的主要運算是檢索有最大鍵值得元素。一般來說，可以容易得把堆修改成使得有最小鍵值得元素存儲在根節(jié)點中。在這種情況下，堆的特性要求存儲在根節(jié)點以外的節(jié)點的鍵值，大于或等于存儲在它父節(jié)點中的鍵值。這兩種類型的堆一般可以看作是最大堆和最小堆。36優(yōu)先級隊列的應(yīng)用1、堆作為一個優(yōu)先級隊列，用于排序嗎？可以！但是，應(yīng)用最多的還是：快速排序。

2、基于最大堆的最大優(yōu)先級隊列。優(yōu)先級隊列：一種用于維護由一組元素構(gòu)成的集合S的數(shù)據(jù)結(jié)構(gòu)。支持如下操作：37INSERT(S，x):MAXIMUM(S)：EXTRACT_MAX(S):去掉并返回S中的具有最大關(guān)鍵字的元素。INCREASE_KEY(S,x,k):將元素x的關(guān)鍵字的值增加到k，這里的k值不能小于x的原關(guān)鍵字的值383、應(yīng)用舉例：分時OS的作業(yè)調(diào)度。應(yīng)用最大堆的優(yōu)先級隊列，記錄需要被調(diào)度的各種作業(yè)以及他們之間的優(yōu)先級的關(guān)系。作業(yè)完成或被中斷時，應(yīng)用EXTRACT_MAX(S)從所有的等待隊列里面選擇一個優(yōu)先級最大的作業(yè)進入調(diào)度，任何時候一個新作業(yè)都可以使用INSERT()操作加入到隊列中。394、小頂堆基于事件驅(qū)動的模擬器（1）隊列中的各項是需要模擬的事件；（2）每一個事件都需要一個發(fā)生事件作為關(guān)鍵字；（3）事件模擬需要按照事件發(fā)生的時間順序進行；（4）一個事件的模擬可能會導(dǎo)致對于稍后對另外一個事件模擬的發(fā)生；（5）新來的模擬事件應(yīng)用INSERT插入隊列404.3不相交集數(shù)據(jù)結(jié)構(gòu)假設(shè)給出一個有n個不同元素的集合S，這些元素被分成不相交集合。最初假設(shè)每個元素自成集合。

下面定義一個m次合并（UNION）和尋找（FIND）運算的序列σ，每次執(zhí)行合并指令后，兩個不相交子集合合并為一個子集。由觀察可知，合并次數(shù)最多是n-1。在每個集合中選擇一個數(shù)據(jù)，用來代表這個集合的名字。{1,2,3,5}標(biāo)記為：5{9,0,8,4}標(biāo)記為：941FIND(x)：尋找并返回包含元素x的集合名字UNION(x,y):包含元素x和y的兩個集合用它們的并集替換。Union合并操作完成后的新集合的名稱標(biāo)記可以或者使用x，或者使用y均可。42用根樹來表示每個集合，集合中的元素存儲在節(jié)點中，樹中除根節(jié)點外的每個元素x都有一個指向父節(jié)點p(x)的指針。

根有一個空指針，用作集合的名字或集合的代表。這樣產(chǎn)生了一個森林，其中每一棵樹對應(yīng)于一個集合。

43

對于任意元素x，用root(x)表示包含x的樹的根。那么，F(xiàn)IND(x)總是返回root(x)。find(x):沿著從x結(jié)點開始直到該樹根結(jié)點的搜索；合并運算由兩棵樹的根作為它的參數(shù)，將假定對于任意兩個元素x和y，

UNION(x,y)實際表示UNION(root(x),root(y))令root(x)的根上的空指針指向root(y)位置。444.3.1按秩合并措施上面講到的合并運算直接實現(xiàn)有一個明顯的缺點，就是樹的高度可能變得非常大，達到尋找運算將需要Ω(n)的時間。在極端情況下，樹可能退化。如：{1},{2},{3},.....{n}按照合并規(guī)則將成為一個“線性樹”1->2->3->4->..........->n45為限制每棵樹的高度，采用按秩合并的措施：給每個節(jié)點存儲一個非負(fù)數(shù)作為該節(jié)點的秩，記為rank，節(jié)點的秩基本上就是它的高度。設(shè)x和y是當(dāng)前森林中兩棵不同的樹的根，初始狀態(tài)時，每個節(jié)點的秩是0，在執(zhí)行運算UNION(x,y)時，比較rank(x)和rank(y)46如果rank(x)<rank(y)，就使y為x的父節(jié)點；如果rank(x)>rank(y)，使x為y的父節(jié)點；(誰大誰當(dāng)?shù)?如果rank(x)=rank(y)，則讓y為x的父節(jié)點，并將rank(y)加1。（修改秩）把這個規(guī)則應(yīng)用到上述運算序列中，得出圖4.6(b)所示的樹?，F(xiàn)在n次尋找運算所用總代價減少到Θ(n)。然而并不總是這樣的，以后會看到，用這種規(guī)則，處理n次尋找運算所需的時間是O(n

logn)。47

令x是任意節(jié)點，p(x)是x的父節(jié)點，有下面兩個基本的觀察結(jié)論。

觀察結(jié)論4.1rank(p(x))≥rank(x)+1//父節(jié)點的秩要至少比子節(jié)點的秩大1。觀察結(jié)論4.2rank(x)的值初始化為0，在后繼合并運算序列中遞增，直到x不再是根節(jié)點。一旦x變成了其他節(jié)點的一個子節(jié)點，它的秩就不再改變了。48引理4.1

包括根節(jié)點x在內(nèi)的樹中節(jié)點的個數(shù)至少是2rank(x)。證明：采用假設(shè)法進行推理。設(shè)存在兩個樹x和y，x、y的秩均為0,上述定理成立?？紤]非0時，未合并操作前，假設(shè)上述定理仍然成立，歸納合并情況如下:（1）rank(x)<rank(y)，則合并成為以y為根的一棵樹,且樹y的節(jié)點數(shù)增加，但rank(y)不變；（2）rank(x)>rank(y),正好與上述情況相反；故rank(x)<>rank(y):上述結(jié)論成立；

(3)rank(x)=rank(y)時,以y為根形成的樹至少應(yīng)該有2(rank(x)）+2（rank(y))=2rank(x)+1個結(jié)點，rank(x)+1成為了樹y的新秩，故上述結(jié)論仍然成立。49顯然如果x是樹T的根，那么T的高度恰好是x的秩。由引理4.1可知，在以x為根的樹中的節(jié)點數(shù)是k，那么樹的高度至多是logk

，所以每次尋找運算的代價是O(log

n)。運算UNION(x,y)所需要的時間分析：（1）如果兩個參數(shù)都是根的話，是O(1)；//直接引指針

50（2）如果x和y不都是根，那么運行時間減少到尋找運算的運行時間。因此，合并運算的時間復(fù)雜性和尋找運算的時間復(fù)雜性相同，都是O(log

n)。

//尋找一個非根數(shù)據(jù)的根節(jié)點，然后引指針可以得出，采用按秩合并措施，m次合并和尋找指令的交替執(zhí)行序列的時間復(fù)雜性是O(mlog

n)。51

4.3.2路徑壓縮

引入背景：對于這種樹存儲集合來講，樹并沒有限定分支（子結(jié)點），所以可以任意增加根節(jié)點的子節(jié)點，而使的集合數(shù)據(jù)不變化，但是由子節(jié)點到根的搜索必然會減少。目標(biāo)：為了后續(xù)的find操作的高效性，故針對已經(jīng)存在的樹集合，進行調(diào)整。

52調(diào)整方法：在一次FIND(x)運算中，找到根節(jié)點y之后，我們再一次遍歷從x到y(tǒng)的路徑，并沿著路徑改變所有節(jié)點指向父節(jié)點的指針，使它們直接指向y。見圖4.753

4.3.3UNION-FIND算法算法FIND和算法UNION描述了用上述兩種措施的尋找和合并運算的最終方案。算法4.6FIND

輸入：節(jié)點x

輸出：root(x),包含x的樹的根

1.yx2.whilep(y)≠null//尋找包含x的樹的根

3.yp(y)

//p(y)指y的父結(jié)點

4.endwhile

//達到根之后結(jié)束循環(huán)

5.rooty;yx

//節(jié)點x存入y中54

6.whilep(y)≠null

//執(zhí)行路徑壓縮

7.w

p(y)//從x依次向上尋找路徑上的結(jié)點，先暫存于w中

8.p(y)root//默認(rèn)以數(shù)組形式存放，則將root存放如p(y)中，即修改當(dāng)前節(jié)點的父節(jié)點標(biāo)識為root。使用指針形式不能這樣寫。

9.yw//取回w10.endwhile11.returnroot55算法4.7UNION

輸入：兩個元素x和y

輸出：包含x和y的兩個樹的合并

1.u

FIND(x);v

FIND(y)2.ifrank(u)≤rank(v)then

3.p(u)v4.ifrank(u)=rank(v)then

rank(v)rank(v)+15.elsep(v)u6.endif56前面已說明，為處理m個合并與尋找的交叉序列,按秩合并在最壞情景下所需時間是O(mlogn)?，F(xiàn)在說明若再使用pathcompression,采用平攤時間分析,可證明時間界限幾乎是O(m+n)。4.3.4Union-Find算法分析57證明：給定秩為r的節(jié)點x,對以x為根的樹中包含的所有節(jié)點都用x標(biāo)號。由引理4.1可知，標(biāo)號的節(jié)點個數(shù)至少是2r。

引理4.2對于任意的整數(shù)r0，秩r的節(jié)點數(shù)至多是n/2r。58如果樹的根節(jié)點發(fā)生變化,那么新樹的根節(jié)點的秩至少是r+1，此說明用x標(biāo)號過的節(jié)點將不再被標(biāo)號。由于標(biāo)過號的節(jié)點個數(shù)最多為n，而且每個秩為r的根至少有2r個節(jié)點，故至多有n/2r個節(jié)點的秩為r。59證明：如果對于某個節(jié)點x，有:rank(x)=rlogn+1，那么由引理4.2可知，至多有n/2logn+1<n/2logn=n/n=1個節(jié)點的秩為r,矛盾。引理4.2說明了秩為r的最多節(jié)點數(shù)。推論4.1任何節(jié)點的秩最大是logn。60定義4.2對于任意整數(shù)，定義為：0若n=0或1Log*n=min{i0|loglog…logn1}若n2.

共i個log例如：Log*2=1,Log*4=2,Log*16=3,Log*65536=4,Log*265536=5。61定義單變量Ackerman函數(shù)F(n)=A(n,n),則有：1若j=0;

F(j)=2F(j-1)若j1.顯然，Log*n=min{j|F(j)n}.F(j)的重要特性是其爆炸性的增長,例如：

F(1)=2，F(xiàn)(2)