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

1、School of Software, YunNan University堆和不相交集數(shù)據(jù)結(jié)構(gòu)2HeJing(2011) School of Software Outline1.堆的定義堆的定義2.堆上的運(yùn)算堆上的運(yùn)算3.堆排序堆排序4.最小堆和最大堆最小堆和最大堆3HeJing(2011) School of Software2.1 2.1 堆的定義堆的定義p在許多算法中，需要支持下面兩種運(yùn)算的數(shù)據(jù)結(jié)在許多算法中，需要支持下面兩種運(yùn)算的數(shù)據(jù)結(jié)構(gòu)：插入元素和尋找最大值構(gòu)：插入元素和尋找最大值n普通隊(duì)列：只能在隊(duì)尾插入元素，但尋找最大元需要普通隊(duì)列：只能在隊(duì)尾插入元素，但尋找最大元需要搜索整個隊(duì)

2、列搜索整個隊(duì)列2022-3-22 A BCDE隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾隊(duì)列隊(duì)列4HeJing(2011) School of Software2.1 2.1 堆的定義堆的定義p在許多算法中，需要支持下面兩種運(yùn)算的數(shù)據(jù)結(jié)在許多算法中，需要支持下面兩種運(yùn)算的數(shù)據(jù)結(jié)構(gòu)：插入元素和尋找最大值構(gòu)：插入元素和尋找最大值n排序數(shù)組：尋找最大元非常簡單，但插入運(yùn)算需要移排序數(shù)組：尋找最大元非常簡單，但插入運(yùn)算需要移動很多元素動很多元素 堆堆2022-3-22 3024201251821635HeJing(2011) School of Software2.1 2.1 堆的定義堆的定義p堆的定義堆的定義：一個（二叉樹）

3、堆是一個幾乎完全的二叉樹，：一個（二叉樹）堆是一個幾乎完全的二叉樹，它的每個節(jié)點(diǎn)都滿足堆的特性：如果它的每個節(jié)點(diǎn)都滿足堆的特性：如果v和和p(v)分別表示節(jié)分別表示節(jié)點(diǎn)和它的父節(jié)點(diǎn)，那么存儲在點(diǎn)和它的父節(jié)點(diǎn)，那么存儲在p(v)中的數(shù)據(jù)項(xiàng)鍵值不小中的數(shù)據(jù)項(xiàng)鍵值不小于存儲在于存儲在v中數(shù)據(jù)項(xiàng)的鍵值。中數(shù)據(jù)項(xiàng)的鍵值。 2022-3-22 302420125182163蘊(yùn)涵：沿著每條從根到葉子的路徑，蘊(yùn)涵：沿著每條從根到葉子的路徑，元素的鍵值以非升序排列。元素的鍵值以非升序排列。6HeJing(2011) School of Software2.1 2.1 堆的定義堆的定義p堆的表示堆的表示：一個有：

4、一個有n個節(jié)點(diǎn)的堆，可以用一個一維數(shù)組個節(jié)點(diǎn)的堆，可以用一個一維數(shù)組H1n來表示。來表示。nT的根節(jié)點(diǎn)存儲在的根節(jié)點(diǎn)存儲在H1中；中；n假設(shè)假設(shè)T的節(jié)點(diǎn)的節(jié)點(diǎn)x存儲在存儲在Hj中，中，則它的左孩子存儲在則它的左孩子存儲在H2j中，中，它的右孩子存儲在它的右孩子存儲在H2j+1中；中；n元素元素Hj的父節(jié)點(diǎn)如果不是根節(jié)點(diǎn)，的父節(jié)點(diǎn)如果不是根節(jié)點(diǎn)，則存儲在則存儲在H 2022-3-22 3024201251821631234567892/ j3024182021631257HeJing(2011) School of Software2.1 2.1 堆的定義堆的定義p如果堆中的節(jié)點(diǎn)有右子節(jié)點(diǎn)，則它

5、一定有左子節(jié)點(diǎn)如果堆中的節(jié)點(diǎn)有右子節(jié)點(diǎn)，則它一定有左子節(jié)點(diǎn)p堆的表現(xiàn)是一棵二叉樹，但它的數(shù)據(jù)結(jié)構(gòu)實(shí)質(zhì)是一個一維堆的表現(xiàn)是一棵二叉樹，但它的數(shù)據(jù)結(jié)構(gòu)實(shí)質(zhì)是一個一維數(shù)組數(shù)組p對于任何索引對于任何索引j，2=j=Hj 2022-3-22 2/ j8HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算pdeletemaxH：從一個非空堆：從一個非空堆H中刪除最大鍵值，中刪除最大鍵值，并返回該值并返回該值pinsertH,x：將：將x插入堆插入堆H中中pdeleteH,i：從堆：從堆H中刪除第中刪除第i項(xiàng)項(xiàng)pmakeheapA：將數(shù)組：將數(shù)組A轉(zhuǎn)換成堆轉(zhuǎn)換成

6、堆 2022-3-22 9HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算p兩個輔助運(yùn)算兩個輔助運(yùn)算Sift_up和和Sift_downn過程：過程：Sift_up（元素上移）（元素上移）n輸入：數(shù)組輸入：數(shù)組H1n和位于和位于1和和n之間的索引之間的索引in輸出：上移輸出：上移Hi，以使，以使H滿足堆的定義滿足堆的定義1.donefalse;2.if i=1 then exit;3.repeat4. if HiH 5. then 交換交換Hi與與H 6. else done true; 7. i ;8.until i=1 or done 20

7、22-3-22 3024201251821631302243184205216673812951035352/ i2/ i2/ i10HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算p兩個輔助運(yùn)算兩個輔助運(yùn)算Sift_up和和Sift_downn過程：過程：Sift_down（元素下移）（元素下移）n輸入：數(shù)組輸入：數(shù)組H1n和位于和位于1和和n之間的索引之間的索引in輸出：上移輸出：上移Hi，以使，以使H滿足堆的定義滿足堆的定義2022-3-22 152243184205216673812930302420125182163524201218

8、216311HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算p兩個輔助運(yùn)算兩個輔助運(yùn)算Sift_up和和Sift_downn過程：過程：Sift_down（元素下移）（元素下移）n輸入：數(shù)組輸入：數(shù)組H1n和位于和位于1和和n之間的索引之間的索引in輸出：上移輸出：上移Hi，以使，以使H滿足堆的定義滿足堆的定義1.donefalse;2.if 2in then exit;3.repeat4. i 2i;5. if i+1Hi then i i+1;6. if H n or done 2022-3-22 2/ i2/ i1522431842052

9、1667381293012HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算pdeletemaxH：從一個非空堆：從一個非空堆H中刪除最大鍵值，中刪除最大鍵值，并返回該值并返回該值pinsertH,x：將：將x插入堆插入堆H中中pdeleteH,i：從堆：從堆H中刪除第中刪除第i項(xiàng)項(xiàng)pmakeheapA：將數(shù)組：將數(shù)組A轉(zhuǎn)換成堆轉(zhuǎn)換成堆 2022-3-22 13HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算pinsertH,x：將：將x插入堆插入堆H中中n算法算法insertn輸入：堆輸入：堆H

10、1n和元素和元素xn輸出：新的堆輸出：新的堆H1n1.nn+1;2.Hn x;3.Sift_up(H,n) 2022-3-22 新堆中的元素個數(shù)新堆中的元素個數(shù)n，則堆的高度為則堆的高度為算法時間復(fù)雜度為：算法時間復(fù)雜度為：O(log n)nlog14HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算pdeleteH,i：從堆：從堆H中刪除第中刪除第i項(xiàng)項(xiàng)n算法算法deleten輸入：非空堆輸入：非空堆H1n和位于和位于1和和n之間的索引之間的索引in輸出：刪除輸出：刪除Hi之后的新堆之后的新堆H1n-11.xHi; yHn;2.if i=n t

11、hen exit; 3.nn-1;4.Hi y;5.if y=x then Sift_up(H,i);6.else Sift_down(H, i);7.endif 2022-3-22 nlog302420125182163算法時間復(fù)雜度：算法時間復(fù)雜度：15HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算pdeletemaxH：從一個非空堆：從一個非空堆H中刪除最大鍵值，并返中刪除最大鍵值，并返回該值回該值n算法算法deletemaxn輸入：堆輸入：堆H1nn輸出：返回最大鍵值輸出：返回最大鍵值x，并將其從堆中刪除，并將其從堆中刪除1.xH1;

12、2.delete(H,1);3.return x 2022-3-22 該算法的時間復(fù)雜度就該算法的時間復(fù)雜度就是刪除算法的時間復(fù)是刪除算法的時間復(fù)雜度：雜度： O(log n)16HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算pmakeheapA ：將數(shù)組：將數(shù)組A轉(zhuǎn)換成堆轉(zhuǎn)換成堆n直接插入法直接插入法：從空堆開始，不斷插入每一個元素，因?yàn)椴迦氲冢簭目斩验_始，不斷插入每一個元素，因?yàn)椴迦氲趈個元素時，所需比較次數(shù)為個元素時，所需比較次數(shù)為log j，用這種方法建堆的復(fù)雜性是，用這種方法建堆的復(fù)雜性是O(nlog n) 2022-3-22 )l

13、og(log)log(log2log2)2log(22nloglog)log(logloglog112/11111nnjnnjnnnnnjnnOjnjnjnjnjnjnjnjnj同理得到：所以）（又即P5217HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算pmakeheapA ：將數(shù)組：將數(shù)組A轉(zhuǎn)換成堆轉(zhuǎn)換成堆n利用二叉樹的性質(zhì)建堆利用二叉樹的性質(zhì)建堆：從第一個非葉節(jié)點(diǎn)開始判斷該子樹是：從第一個非葉節(jié)點(diǎn)開始判斷該子樹是否是一個堆，如果不是，則調(diào)用否是一個堆，如果不是，則調(diào)用Sift_down算法構(gòu)造堆算法構(gòu)造堆n算法：算法：MakeHeapn

14、輸入：輸入：n個元素的數(shù)組個元素的數(shù)組A1nn輸出：輸出：A1n轉(zhuǎn)換成的堆轉(zhuǎn)換成的堆1.for i downto 12. Sift_down(A, i);3.endfor 2022-3-22 2/n431030178111371423384105116137783091718HeJing(2011) School of Software2.2 2.2 堆上的運(yùn)算堆上的運(yùn)算pmakeheapA ：將數(shù)組：將數(shù)組A轉(zhuǎn)換成堆轉(zhuǎn)換成堆n利用二叉樹的性質(zhì)建堆利用二叉樹的性質(zhì)建堆：從第一個非葉節(jié)點(diǎn)開始判斷該子樹是：從第一個非葉節(jié)點(diǎn)開始判斷該子樹是否是一個堆，如果不是，則調(diào)用否是一個堆，如果不是，則調(diào)用Si

15、ft_down算法構(gòu)造堆算法構(gòu)造堆n假設(shè)堆的高為假設(shè)堆的高為k=|log n|nn=20+21+22+2k-1+r 2022-3-22 4310301781113714233841051161377830917nkikiiikkkiikkkiikiikiki2)2(2*222222214. 250P222)(11110所以：公式：根據(jù)p元素比較的總次數(shù)上界是元素比較的總次數(shù)上界是4n19HeJing(2011) School of Software2.3 2.3 堆排序堆排序p堆排序堆排序 把所有要排序的元素構(gòu)造成一個堆，然后刪去根節(jié)點(diǎn)上的把所有要排序的元素構(gòu)造成一個堆，然后刪去根節(jié)點(diǎn)上的元素

16、。刪去最大深度的最右邊的葉元素，將其移至根上，元素。刪去最大深度的最右邊的葉元素，將其移至根上，將這棵樹再變成一個堆。以后，重復(fù)上述過程，直到這棵將這棵樹再變成一個堆。以后，重復(fù)上述過程，直到這棵樹只剩一個頂點(diǎn)為止。從這個堆的根節(jié)點(diǎn)上刪去的元素序樹只剩一個頂點(diǎn)為止。從這個堆的根節(jié)點(diǎn)上刪去的元素序列（按刪去的先后順序排列起來）就是一個排序好的非遞列（按刪去的先后順序排列起來）就是一個排序好的非遞增序列增序列p(最壞情況下時間復(fù)雜度為最壞情況下時間復(fù)雜度為O(nlog2n)2022-3-22 20HeJing(2011) School of Software2.3 2.3 堆排序堆排序p堆排序的過

17、程是，把初始數(shù)據(jù)堆排序的過程是，把初始數(shù)據(jù)“堆化堆化”后，重復(fù)執(zhí)行如下后，重復(fù)執(zhí)行如下兩個步驟：兩個步驟：1. 刪除根節(jié)點(diǎn)的元素；刪除根節(jié)點(diǎn)的元素；2. 將最深最右的葉元將最深最右的葉元素移到根節(jié)點(diǎn)并刪去這個葉；素移到根節(jié)點(diǎn)并刪去這個葉；3.重新堆化。重新堆化。p在實(shí)際處理時，只需將根節(jié)點(diǎn)元素和待刪葉元素互換，就在實(shí)際處理時，只需將根節(jié)點(diǎn)元素和待刪葉元素互換，就能達(dá)到刪除根節(jié)點(diǎn)元素和把最深最右的葉元素移至根節(jié)點(diǎn)能達(dá)到刪除根節(jié)點(diǎn)元素和把最深最右的葉元素移至根節(jié)點(diǎn)上的雙重目的，然后對剩下的元素重新堆化。上的雙重目的，然后對剩下的元素重新堆化。p例：對例：對50，24，30，20，21，18，3，1

18、2，5，6進(jìn)進(jìn)行堆排序。行堆排序。2022-3-22 21HeJing(2011) School of Software2.3 2.3 堆排序堆排序例:對50，24，30，20，21，18，3，12，5，6進(jìn)行堆排序。下列的圖表示刪去根元素和重新堆化的過程。50242012530211836(i)624201253021183(ii) 刪去刪去50，將，將6移至根部移至根部2022-3-22 22HeJing(2011) School of Software2.3 2.3 堆排序堆排序如果用數(shù)組記錄上述過程，數(shù)組元素的變化如下：如果用數(shù)組記錄上述過程，數(shù)組元素的變化如下：(i) 50，24，3

19、0，20，21，18，3，12，5，6(ii) 6， 24，30，20，21，18，3，12，5， 50(iii) 30， 24，6，20，21，18，3，12，5， 50(iv) 30， 24，18，20，21，6，3，12，5， 50302420125621183(iii) 將將6與它的最大兒子與它的最大兒子30交換交換302420125182163(iv) 將將6與它的最大兒子與它的最大兒子18交換交換2022-3-22 23HeJing(2011) School of Software2.3 2.3 堆排序堆排序p算法算法HeapSortp輸入：輸入：n個元素的數(shù)組個元素的數(shù)組A1np

20、輸出：以非將序排列的數(shù)組輸出：以非將序排列的數(shù)組A1.MakeHeap(A);2.for j n downto 23. 交換交換A1和和Aj;4. Sift_down(A1j-1, 1);5.endfor2022-3-22 不需要額外的臨時不需要額外的臨時數(shù)組，空間復(fù)數(shù)組，空間復(fù)雜性是：雜性是：(1)(1)時間復(fù)雜性是：時間復(fù)雜性是：O(nlogn)O(nlogn)24HeJing(2011) School of Software2.3 2.3 堆排序堆排序p定理定理 算法算法HEAPSORT對對n個元素排序所需的時間是個元素排序所需的時間是O(nlog2n)。p堆排序的優(yōu)點(diǎn)是使用空間少，數(shù)據(jù)

21、結(jié)構(gòu)簡單，只需數(shù)組堆排序的優(yōu)點(diǎn)是使用空間少，數(shù)據(jù)結(jié)構(gòu)簡單，只需數(shù)組A1:n占用的空間占用的空間p準(zhǔn)確來說，準(zhǔn)確來說，T(n)=2nlog2n+O(n)2022-3-22 )()log()(122nOiOnTni25HeJing(2011) School of Software2.4 2.4 最大堆與最小堆最大堆與最小堆p最大堆：根節(jié)點(diǎn)為最大元素，且二叉樹中每一個節(jié)點(diǎn)滿足最大堆：根節(jié)點(diǎn)為最大元素，且二叉樹中每一個節(jié)點(diǎn)滿足堆的性質(zhì)堆的性質(zhì)p最小堆：根節(jié)點(diǎn)為最小元素，且二叉樹中每一個節(jié)點(diǎn)滿足最小堆：根節(jié)點(diǎn)為最小元素，且二叉樹中每一個節(jié)點(diǎn)滿足堆的性質(zhì)堆的性質(zhì)p堆是一種相當(dāng)好的數(shù)據(jù)結(jié)構(gòu)，具有非常優(yōu)越的性

22、能。利用堆是一種相當(dāng)好的數(shù)據(jù)結(jié)構(gòu)，具有非常優(yōu)越的性能。利用它，可以實(shí)現(xiàn)另一個實(shí)用的類它，可以實(shí)現(xiàn)另一個實(shí)用的類優(yōu)先隊(duì)列（優(yōu)先隊(duì)列有優(yōu)先隊(duì)列（優(yōu)先隊(duì)列有著廣泛的應(yīng)用著廣泛的應(yīng)用,在操作系統(tǒng)中在操作系統(tǒng)中,許多消息隊(duì)列、等待隊(duì)列等許多消息隊(duì)列、等待隊(duì)列等,使用了優(yōu)先隊(duì)列，在算法中，我們常用優(yōu)先隊(duì)列來實(shí)現(xiàn)廣使用了優(yōu)先隊(duì)列，在算法中，我們常用優(yōu)先隊(duì)列來實(shí)現(xiàn)廣度搜索、貪心算法等）。還可以高效實(shí)現(xiàn)哈夫曼編碼，可度搜索、貪心算法等）。還可以高效實(shí)現(xiàn)哈夫曼編碼，可以使以使n2的的Dijkstra算法復(fù)雜度降至算法復(fù)雜度降至nlogn。2022-3-22 26HeJing(2011) School of Software2.5 2.5 不相交集數(shù)據(jù)結(jié)構(gòu)不相交集數(shù)據(jù)結(jié)構(gòu)p假設(shè)給定一個有假設(shè)給定一個有n個不相同元素的集合個不相同元素的集合S，這些元素被劃，這些元素被劃分為不相交集合。分為不相交集合。nFind(x)：尋找并返回包含元素：尋找并返回包含