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

堆和不相交數(shù)據(jù)結(jié)構(gòu)第1頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三二叉樹性質(zhì)(Page71)性質(zhì)1：在二叉樹中，第j層的頂點(diǎn)數(shù)最多是2j。性質(zhì)2：令二叉樹T頂點(diǎn)數(shù)是n，高度是k，那么如果T是完全的，等號(hào)成立。如果T是幾乎完全的，那么性質(zhì)3：有n個(gè)頂點(diǎn)的完全或幾乎完全的二叉樹的高度是性質(zhì)4：對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+12第2頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三性質(zhì)：對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1證明：n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù)因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2

又二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè)分支進(jìn)入設(shè)B為分支總數(shù)，則n=B+1

又：分支由度為1和度為2的結(jié)點(diǎn)射出，B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1第3頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1in)，有：

(1)如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無(wú)雙親；如果i>1，則其雙親是i/2(2)如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子；如果2in，則其左孩子是2i(3)如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；如果2i+1n，則其右孩子是2i+14第4頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.1引言（堆、不相交集）4.2堆

4.2.1堆上的運(yùn)算

4.2.2創(chuàng)建堆

4.2.3堆排序

4.2.4最大堆和最小堆4.3不相交集數(shù)據(jù)結(jié)構(gòu)

4.3.1按秩合并措施

4.3.3

Union-Find算法

4.3.2路徑壓縮4.3.4Union-Find算法的分析（略）5第5頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.2堆㈠堆的引入在許多算法中，需要支持下面二種運(yùn)算： 插入元素 尋找最大值元素（或最小值元素）支持這二種運(yùn)算的數(shù)據(jù)結(jié)構(gòu)稱為優(yōu)先隊(duì)列?？刹捎孟率鋈N方法實(shí)現(xiàn)優(yōu)先隊(duì)列：使用普通隊(duì)列（或數(shù)組），插入容易（尾部），但尋找最大值需搜索整個(gè)隊(duì)列，開銷比較大。使用排序數(shù)組，尋找最大值元素容易，插入操作需移動(dòng)很多元素。使用堆，尋找最大值元素容易，插入操作僅需移動(dòng)少量元素。6第6頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三定義4.1（Page74）一個(gè)（二叉）堆是一棵幾乎完全的二叉樹，它的每個(gè)結(jié)點(diǎn)都滿足堆的特性：設(shè)v是一個(gè)結(jié)點(diǎn)，p(v)是v的父結(jié)點(diǎn)，那么存儲(chǔ)在p(v)中的數(shù)據(jù)項(xiàng)鍵值大于或等于存儲(chǔ)在v中的數(shù)據(jù)項(xiàng)鍵值。㈡堆的定義（二叉堆）

幾乎完全二叉樹（Page71）如果一棵二叉樹，除了最右邊位置上的一個(gè)或幾個(gè)葉子可能缺少外，它是豐滿的，我們定義它為幾乎完全二叉樹。①② ③④ ⑤ ⑥ ⑦⑧⑨⑩幾乎完全二叉樹例7第7頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三堆數(shù)據(jù)結(jié)構(gòu)支持下列運(yùn)算DeleteMax(H)：從一個(gè)非空堆H中，刪除最大鍵值的數(shù)據(jù)項(xiàng)，并返回該數(shù)據(jù)；Insert(H,x)：將數(shù)據(jù)項(xiàng)x插入堆H中；Delete(H,i)：從堆中刪除第i項(xiàng)；MakeHeap(A)：將數(shù)組轉(zhuǎn)換為堆。堆的蘊(yùn)含特性：沿著每條從根到葉子的路徑，元素的鍵值以降序（或稱非升序）排列。8第8頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三㈢堆的表示有n個(gè)結(jié)點(diǎn)堆T，可以用一個(gè)數(shù)組H[1..n]用下面方式來(lái)表示：T的根結(jié)點(diǎn)存儲(chǔ)在H[1]中；設(shè)T的結(jié)點(diǎn)存儲(chǔ)在H[j]中，如果它有左子結(jié)點(diǎn)，則這個(gè)左子結(jié)點(diǎn)存儲(chǔ)在H[2j]中。如果它還有右子結(jié)點(diǎn)，這個(gè)右子結(jié)點(diǎn)存儲(chǔ)在H[2j+1]；若元素H[j]不是根結(jié)點(diǎn)，它的父結(jié)點(diǎn)存儲(chǔ)在H[j/2]中。由“幾乎完全二叉樹”的定義可知，如果堆中某結(jié)點(diǎn)有右子結(jié)點(diǎn)，則它一定也有左子結(jié)點(diǎn)。堆具有如下性質(zhì)：

key(H[j/2])≥key(H[j])

2≤j≤n9第9頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三201172 93104 115 46 5738 79 510

㈣堆和它的數(shù)組表示法把存儲(chǔ)在堆中的數(shù)據(jù)項(xiàng)視為鍵值。按樹的結(jié)點(diǎn)“自頂向下”、“從左至右”、“按1到n”的順序進(jìn)行編號(hào)，那么數(shù)組元素H[i]對(duì)應(yīng)樹中編號(hào)為i的結(jié)點(diǎn)。2017910114537512345678910H[2]=17的左子結(jié)點(diǎn)為H[2*2]=H[4]=10H[2]=17的右子結(jié)點(diǎn)為H[2*2+1]=H[5]=11H[9]=7的父結(jié)點(diǎn)為H[9/2

]=H[4]=10沿著每條從根到葉子的路徑，元素的鍵值以降序排列。10第10頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.2.1堆上的運(yùn)算㈠ShiftUp

假定對(duì)于某個(gè)i＞1，H[i]的鍵值變成大于它父結(jié)點(diǎn)的鍵值，這樣違反了堆的特性，需使用稱為ShiftUp的運(yùn)算來(lái)修復(fù)堆。

ShiftUp運(yùn)算沿著從H[i]到根結(jié)點(diǎn)的惟一路徑，把H[i]移到適合它的位置上。在移動(dòng)的每一步中，將H[i]的鍵值與它的父結(jié)點(diǎn)H[i/2]的鍵值相比較，若若H[i]＞H[i/2]，則H[i]和H[i/2]互換（上移），繼續(xù)。若H[i]≤H[i/2]或i＝1，終止。11第11頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三②H[5]=25＞H[2]=17，互換。互換后H[5]=17、H[2]=25；①H[10]=25＞H[5]=11，互換?；Q后H[10]=11、H[5]=25；H[10]的鍵值由5變?yōu)?520179101145372512345678910③H[2]=25＞H[1]=20，互換?；Q后H[2]=20、H[1]=25；25209101745371120179102545371120259101745371120117291041155104537④H[1]=25位于根結(jié)點(diǎn)。此時(shí)i=1，程序終止。251012第12頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三過(guò)程ShiftUp（參見Page75）輸入：數(shù)組H[1..n]和索引i（1≤i≤n）輸出：上移H[i](如果需要)，使它不大于父結(jié)點(diǎn)。1. done←false2. ifi＝1thenexit //根結(jié)點(diǎn)3. repeat4. ifkey(H[i])＞key(H[i/2])then5. 互換H[i]和H[i/2]6. else7. done←true8. endif9. i←i/210. until(i=1)ordone13第13頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三㈡ShiftDown假定對(duì)于某個(gè)i≤

n/2（非葉結(jié)點(diǎn)），H[i]的鍵值變成小于它的左右子結(jié)點(diǎn)H[2i]或H[2i+1]的鍵值，這樣違反了堆的特性，需使用稱為ShiftDown的運(yùn)算來(lái)修復(fù)堆。ShiftDown運(yùn)算使H[i]下移到二叉樹中適合它的位置上。在下移的每一步中，將H[i]的鍵值與它的子結(jié)點(diǎn)鍵值相比較，若H[i]＜子結(jié)點(diǎn)鍵值，則H[i]與子結(jié)點(diǎn)鍵值中較大者交換（下移），繼續(xù)；H[i]≥子結(jié)點(diǎn)鍵值或i＞n/2，終止。說(shuō)明：H[i]應(yīng)與它的子結(jié)點(diǎn)中鍵值較大者交換，被交換者將成為原堆中另一個(gè)鍵值較小的子結(jié)點(diǎn)的父結(jié)點(diǎn)（如果有的話）。1710 111110 3314第14頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三⑵說(shuō)明：若i＞n/2，則該結(jié)點(diǎn)位于葉子的位置，無(wú)需下移。①② ③④ ⑤ ⑥ ⑦⑧⑨⑩①② ③④ ⑤⑥⑦⑧⑨⑩○

○○○○n/2=15/2=7n/2=10/2=515第15頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三H[2]鍵值由17變?yōu)?20391011453751234567891020119105453732011910345375②H[5]=3小于H[10]=5，所以H[5]和H[10]互換。交換后H[5]=5，H[10]=3；③H[10]=3位于葉結(jié)點(diǎn)位置。i=10>n/2=5，程序終止。①H[2]=3小于H[4]和H[5]，因?yàn)镠[4]<H[5]，所以H[2]和H[5]互換。交換后H[2]=11，H[5]=3；20117293104115453753216第16頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三過(guò)程ShiftDown（Page76）輸入：數(shù)組H[1..n]和索引i（1≤i≤n）輸出：下移H[i]（如果需要），使它不小于子結(jié)點(diǎn)。1. done←false2. if2i＞nthenexit //H[i]是葉結(jié)點(diǎn)，無(wú)需下移。3. repeat4. i←2i

//i指向子結(jié)點(diǎn)5. if(i+1≤n)and(key(H[i+1])＞key(H[i]))then6.

i←i+1 //若有右子結(jié)點(diǎn)，選擇子結(jié)點(diǎn)較大者。7. endif8. ifkey(H[i/2])<key(H[i])then9. 互換H[i]和H[i/2]10. else11. done←true12. endif13. until(2i>n)ordone17第17頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三㈢插入為了把元素x插入堆H中，先將堆的大小增1，然后元素x添加到H的末尾，再根據(jù)需要將x上移，直到滿足堆的特性。若新堆的個(gè)數(shù)為n，那么堆樹的高度為log2n所以將一個(gè)元素插入大小為n的堆中所需要的時(shí)間為O(log2n)算法4.1Insert（77）輸入：堆H[1..n]和元素x輸出：新堆H[1..n+1]，x為其元素之一。1. n←n+12. H[n]←x3. ShiftUp(H,n)18第18頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三㈣刪除

要從大小為n的堆中刪除元素H[i]，可先用H[n]替換H[i]，然后將堆的大小減1。設(shè)原H[i]的鍵值為key(x)，原H[n]的鍵值為key(y)， 若key(y)≥key(x)，則執(zhí)行上移y。

若key(y)＜key(x)，則執(zhí)行下移y。若i=1，則表示刪除堆的最大值。由于堆樹的高度為log2n，所以刪除一個(gè)元素所需的時(shí)間為O(log2n)。19第19頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三算法4.2Delete（Page77）輸入：非空堆H[1..n]和索引i（1≤i≤n）輸出：刪除H[i]的新堆H[1..n-1]1. x←H[i]:y←H[n] //H[i]為要?jiǎng)h除的元素2. n←n-13. ifi＝n+1thenexit //刪除堆最后一個(gè)元素4. H[i]←y5. ifkey(y)≥key(x)then6. ShiftUp(H,i)7. else8. ShiftDown(H,i)9. endif20第20頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.2.2創(chuàng)建堆①方法一給出有n個(gè)元素的數(shù)組A[1..n]，要?jiǎng)?chuàng)建一個(gè)包含這些元素的堆可以這樣進(jìn)行：首先假設(shè)堆由1個(gè)元素構(gòu)成，然后將第2個(gè)、第3個(gè)元素插入堆，直至n個(gè)。插入第i個(gè)元素，上移次數(shù)(循環(huán)次數(shù))最多為log2i，因此采用這種方法創(chuàng)建堆的時(shí)間復(fù)雜性為O(nlog2n)。算法MakeHeapByInsert（參見Page77）輸入：n個(gè)元素的數(shù)組A[1..n]輸出：堆A[1..n]1. fori＝2ton2. ShiftUp(A,i)3. endfor21第21頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.15給出一個(gè)整數(shù)數(shù)組A[1..n]，可按照下面的方法建立一個(gè)A的堆B[1..n]。從空堆開始，反復(fù)將A中元素插入B，每一次調(diào)整當(dāng)時(shí)的堆，直到B包含A中的所有元素。證明在最壞情況下，算法運(yùn)行時(shí)間是Θ(nlogn)。解：1. fori←1ton2. B[i]←A[i]3. ShiftUp(B,i) //ShiftUp(B[1..i],i)4. endfor在最壞情況下

22第22頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.16用圖說(shuō)明練習(xí)4.15的算法對(duì)于下面數(shù)組的運(yùn)算。解：

A[1..8]＝69271843B[1..1]=669969629627972697261972618978612978612497861243B[1..8]=B[1..2]=B[1..3]=B[1..4]=B[1..5]=B[1..7]=B[1..6]=23第23頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三②方法二設(shè)數(shù)組A有n=10個(gè)元素，構(gòu)造它的幾乎完全二叉樹T，如下所示，顯然T不是堆。438101113730172612345678910觀察數(shù)組A的元素：A[n/2+1]=A[6]，……，A[n]=A[10]，它們對(duì)應(yīng)于T的葉子。這樣調(diào)整可以從內(nèi)部結(jié)點(diǎn)開始，先調(diào)整A[n/2]=A[5]，隨后調(diào)整A[n/2-1]=A[4]，…，直至A[1]。41328310411513677308179261024第24頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三41

32 83

104

115 136 77

308179

2610

438101113730172612345678910A[n/2]=A[5]=11A[n/2-1]=A[4]=10A[n/2-2]=A[3]=8A[n/2-3]=A[2]=3

A[n/2-4]=A[1]=44381026137301711438302613710171143133026871017114301332687101711430131726871031130413172687103113026131748710311302613171187103425第25頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三算法MakeHeap(Page79)輸入：n個(gè)元素的數(shù)組A[1..n]輸出：堆A[1..n]1. fori←n/2downto12. ShiftDown(A,i)3. endfor設(shè)樹T的高度為k=log2n，令A(yù)[j]為對(duì)應(yīng)于樹的第i層中的第j個(gè)結(jié)點(diǎn)，執(zhí)行ShiftDown(A,j)運(yùn)算，下移次數(shù)(即循環(huán)次數(shù))最多為k-i。因?yàn)樵诘趇層恰好有2i個(gè)結(jié)點(diǎn)，故執(zhí)行總的下移次數(shù)的上界為：20(k-0)+21(k-1)+22(k-2)+…+2k-3(3)+2k-2(2)+2k-1(1)26第26頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三○○○○○○○第0層結(jié)點(diǎn)下移最多次數(shù)20(k-0)令k=log2n，設(shè)n=31則k=4。○○○○○第1層結(jié)點(diǎn)下移最多次數(shù)21(k-1)第i層結(jié)點(diǎn)下移最多次數(shù)2i(k-i)第k-1層結(jié)點(diǎn)下移最多次數(shù)2k-1(k-(k-1))=2k-1(1)設(shè)樹T的高度為k＝log2n，令A(yù)[j]為對(duì)應(yīng)于樹的第i層中的第j個(gè)結(jié)點(diǎn)，執(zhí)行ShiftDown(A,j)運(yùn)算，下移次數(shù)(即循環(huán)次數(shù))最多為k-i。因?yàn)樵诘趇層恰好有2i個(gè)結(jié)點(diǎn)，故執(zhí)行總的下移次數(shù)的上界為:20(k-0)+21(k-1)+22(k-2)+…+2k-3(3)+2k-2(2)+2k-1(1)第2層結(jié)點(diǎn)下移最多次數(shù)22(k-2)27第27頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三可參考本書Page50（式2.14）28第28頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三定理4.1（Page79）使用算法MakeHeap構(gòu)造一個(gè)n元素的堆，令C(n)為執(zhí)行該算法的元素比較次數(shù)，那么n-1≤C(n)＜4n因此構(gòu)造一個(gè)n個(gè)元素的堆，算法MakeHeap需要Θ(n)時(shí)間和Θ(1)空間。

在過(guò)程ShiftDown的每一次循環(huán)中，最多有二次元素比較（有二個(gè)if語(yǔ)句），因此元素總的比較次數(shù)上界為2*2n。同時(shí)過(guò)程ShiftDown至少執(zhí)行一次循環(huán)，所以元素的最少比較次數(shù)由內(nèi)部結(jié)點(diǎn)數(shù)決定，元素總的比較次數(shù)下界為2n/2≥n-1（若原為堆）。29第29頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.2.3堆排序

給定數(shù)組A[1..n]，設(shè)每個(gè)元素的鍵值是該元素本身，可采用如下方法進(jìn)行排序：使用算法MakeHeap將數(shù)組A變換成堆。首先將A[1]和A[n]交換，顯然A[n]為數(shù)組中最大元素，然后調(diào)用過(guò)程ShiftDown將A[1..n-1]轉(zhuǎn)換成堆。接著將A[1]和A[n-1]交換，顯然A[n-1]為數(shù)組中次最大元素，然后調(diào)用過(guò)程ShiftDown將A[1..n-2]轉(zhuǎn)換成堆。交換元素和堆調(diào)整過(guò)程一直重復(fù)，直至堆的大小為1。30第30頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三算法4.5HeapSort(Page80)輸入：n個(gè)元素的數(shù)組A輸出：數(shù)組A中元素按升序排列1. MakeHeap(A)2. forj←ndownto23. 互換A[1]和A[j]4. ShiftDown(A[1..j-1],1)5. endfor

這個(gè)算法在原有空間進(jìn)行排序，建立堆用Θ(n)時(shí)間，ShiftDown運(yùn)算用O(log2n)時(shí)間，并且重復(fù)n-1次。參考習(xí)題4.1431第31頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三

這個(gè)算法在原有空間進(jìn)行排序，建立堆用Θ(n)時(shí)間，ShiftDown運(yùn)算用O(log2n)時(shí)間，并且重復(fù)n-1次，顯然建立堆所用的時(shí)間為低次項(xiàng)，可略。定理4.2(Page80)算法HeapSort對(duì)n個(gè)元素排序，需要用O(nlog2n)時(shí)間和Θ(1)空間。由此可見，堆排序是最優(yōu)秀的排序算法。4.2.4最大堆和最小堆最大堆：最大鍵值元素存放在根結(jié)點(diǎn)。最小堆：最小鍵值元素存放在根結(jié)點(diǎn)。32第32頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.3不相交集數(shù)據(jù)結(jié)構(gòu)（并查集）是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（DisjointSets）的合并及查詢問(wèn)題。如數(shù)據(jù)結(jié)構(gòu)課中講到的最小生成樹Kruskal算法：Kruskal是一種貪心算法，比較適用于稀疏圖:為使生成樹上邊的權(quán)值和最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。具體做法:找出森林中連接任意兩棵樹的所有邊中，具有最小權(quán)值的邊，如果將它加入生成樹中不產(chǎn)生回路，則它就是生成樹中的一條邊。這里的關(guān)鍵就是如何判斷"將它加入生成樹中不產(chǎn)生回路"。33第33頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.3不相交集數(shù)據(jù)結(jié)構(gòu)㈠不相交集合及運(yùn)算設(shè)集合S有n個(gè)元素，這些元素被分成若干個(gè)不相交子集。最初假設(shè)每個(gè)元素自成一個(gè)集合，這樣共有n個(gè)子集。經(jīng)n次合并（Union）后，構(gòu)成若干個(gè)不相交子集。每個(gè)子集用該子集中一個(gè)特殊元素命名。例：假定n個(gè)元素的集合S={1,2,3,4,5,6,7,8,9,10,11}⑴最初有11個(gè)子集 {1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}

每個(gè)子集的名稱分別為子集中元素本身。⑵經(jīng)若干次合并后，形成4個(gè)子集，假設(shè)它們是 {1,7,10,11},{2,3,5,6},{4,8},{9}4個(gè)子集依次被命名為1、3、8、9。34第34頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三我們對(duì)Union和Find二種不相集運(yùn)算定義如下：Find(x)：尋找并返回包含元素x的集合名字。Union(x,y)：將包含元素x和y的二個(gè)集合用它們的并集替換。并集的名字，或?yàn)榘豿的那個(gè)集合的名字，或?yàn)榘貀的那個(gè)集合的名字。我們目的是設(shè)計(jì)這二種運(yùn)算的有效算法，為此需要一種數(shù)據(jù)結(jié)構(gòu)，它既要簡(jiǎn)單，又要能有效實(shí)現(xiàn)合并和尋找這二種運(yùn)算。35第35頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三㈡不相交集數(shù)據(jù)結(jié)構(gòu)①將用于命名子集名稱的元素視為根，其余元素視為其后代，每個(gè)子集可用一棵根樹來(lái)表示，這樣便形成了森林。9②每個(gè)結(jié)點(diǎn)都有一個(gè)指針。非根結(jié)點(diǎn)的指針指向它的父結(jié)點(diǎn)；根結(jié)點(diǎn)的指針值為0，表示不指向任何結(jié)點(diǎn)。③根結(jié)點(diǎn)用作集合的名字。④森林可方便地用數(shù)組A[1..n]。A[j]是j的父結(jié)點(diǎn)，若A[j]=0，說(shuō)明j是根結(jié)點(diǎn)。⑤對(duì)于任一元素x，用root(x)表示包含x的樹的根，例root(6)=3。03082210011123456789101184171011325636第36頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三㈢不相交集運(yùn)算實(shí)現(xiàn)①Find(x)尋找并返回包含元素x的樹的根。例， Find(6)=root(6)=3②Union(x,y)

將包含x和y的二個(gè)不相交集合并成一個(gè)集合，也就是說(shuō)把二棵樹合并成一棵樹，Union(x,y)可表示為Union(root(x),root(y))。若合并后樹的根為root(x)，則有A[root(y)]=root(x)。若合并后樹的根為root(y)，則有A[root(x)]=root(y)。84984 9或984例，Union(4,9)=Union(root(4),root(9))=Union(8,9)8001234567891011837第37頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.3.1按秩合并措施nn-1……21㈠問(wèn)題的提出若直接進(jìn)行合并運(yùn)算有個(gè)明顯缺點(diǎn)，在極端情況下，樹有可能退化成線性表。假定從單元素集合{1},{2},…,{n}開始，執(zhí)行下面的合并序列（假設(shè)第二個(gè)參數(shù)為合并后樹的根）： Union(1,2),Union(2,3),…,Union(n-1,n)形成的樹如左圖所示。執(zhí)行下面的尋找序列： Find(1),Find(2),…,Find(n)n次尋找運(yùn)算總的代價(jià)為：38第38頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三㈡引入秩

為了限制每棵樹的高度，采用秩合并的措施。給每個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)非負(fù)數(shù)作為該結(jié)點(diǎn)的秩（記為rank），初始時(shí)每個(gè)結(jié)點(diǎn)的秩均為0。設(shè)x和y是二棵不同樹的根，執(zhí)行Union(x,y)時(shí)，比較rank(x)和rank(y)，若rank(x)<rank(y)，則使y成為x的父結(jié)點(diǎn)，rank(x)和rank(y)不變。rank(x)=rank(y)，則使y成為x的父結(jié)點(diǎn)，rank(y)增1，rank(x)不變（或相反）。rank(x)>rank(y)，則使x成為y的父結(jié)點(diǎn)，rank(x)和rank(y)不變。39第39頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三x1100y2215060y1100x221506071100y2215060x2rank(x)<rank(y)，則使y成為x的父結(jié)點(diǎn)，rank(x)和rank(y)不變。rank(x)=rank(y)，則使y成為x的父結(jié)點(diǎn)，rank(y)增1，rank(x)不變（或相反）。rank(x)>rank(y)，則使x成為y的父結(jié)點(diǎn)，rank(x)和rank(y)不變。y240第40頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三令x是任意結(jié)點(diǎn)，p(x)是x的父結(jié)點(diǎn)，有下面二個(gè)基本觀察結(jié)論。觀察結(jié)論4.1(Page82)rank(p(x))＞rank(x)觀察結(jié)論4.2(Page82)rank(x)的值初始化為0，在后繼合并運(yùn)算序列中遞增，直到x不是根結(jié)點(diǎn)。一旦x變成了其它樹的子結(jié)點(diǎn)，它的秩就不再改變。41第41頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三4.3.3Union-Find算法算法4.6Find（參見Page83)輸入：結(jié)點(diǎn)x輸出：root(x) ，包含x的樹的根。0.procedureFind(x)1. y←x2. whilep(y)≠0 //p(y)=0表示y是根結(jié)點(diǎn)3. y←p(y)4. endwhile5. root←y6. returnroot7.endprocedure //注：路徑壓縮被略去42第42頁(yè)，講稿共49頁(yè)，2023年5月2日，星期三算法4.7Union(Page83)輸入：結(jié)點(diǎn)x和y輸出：包含x和y的二棵樹的合并0.procedureUnion(x,y)1. u←Find(x):v←Find(y)2. ifrank(u)≤rank(v)then3. p(u)←v//包含y的樹的根結(jié)點(diǎn)v是合并后的根結(jié)點(diǎn)4. ifrank(u)=rank(v)then5. rank(v)=rank(v)+16. endif7. else//rank(u)>rank(v)8. p(v)←u//包含x的樹的根結(jié)點(diǎn)