數(shù)據(jù)結(jié)構(gòu)與算法分析第六章_優(yōu)先隊(duì)列(堆)

1、第六章第六章 優(yōu)先隊(duì)列優(yōu)先隊(duì)列(堆堆)2本章綱要本章綱要n1.優(yōu)先隊(duì)列模型優(yōu)先隊(duì)列模型n2.二叉堆二叉堆n3.優(yōu)先隊(duì)列的應(yīng)用優(yōu)先隊(duì)列的應(yīng)用n4.d-堆堆n5.左式堆左式堆n6.斜堆斜堆n7.二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列31.優(yōu)先隊(duì)列模型優(yōu)先隊(duì)列模型n隊(duì)列隊(duì)列nFIFOn排隊(duì)等候買票排隊(duì)等候買票n優(yōu)先級(jí)優(yōu)先級(jí)n例如，救護(hù)車過紅燈例如，救護(hù)車過紅燈n對(duì)隊(duì)列而言，隊(duì)首元素先出隊(duì)，暗含了隊(duì)首對(duì)隊(duì)列而言，隊(duì)首元素先出隊(duì)，暗含了隊(duì)首優(yōu)先級(jí)最高。優(yōu)先級(jí)最高。41.優(yōu)先隊(duì)列模型優(yōu)先隊(duì)列模型n優(yōu)先隊(duì)列優(yōu)先隊(duì)列n隊(duì)列中元素具有不同的優(yōu)先級(jí)，優(yōu)先級(jí)高的隊(duì)列中元素具有不同的優(yōu)先級(jí)，優(yōu)先級(jí)高的元素先出隊(duì)（元素先出隊(duì)（deque）n

2、遵守隊(duì)列隊(duì)首先出隊(duì)的規(guī)則遵守隊(duì)列隊(duì)首先出隊(duì)的規(guī)則n因此，在優(yōu)先隊(duì)列中，優(yōu)先級(jí)最高的元素應(yīng)因此，在優(yōu)先隊(duì)列中，優(yōu)先級(jí)最高的元素應(yīng)在隊(duì)首。在隊(duì)首。n入隊(duì)（入隊(duì)（enque）插入（插入（insert）n出隊(duì)（出隊(duì)（deque）（deletemin）51.優(yōu)先隊(duì)列模型優(yōu)先隊(duì)列模型n實(shí)現(xiàn)實(shí)現(xiàn)n鏈表鏈表n數(shù)組數(shù)組n二叉查找樹二叉查找樹62.二叉堆二叉堆n若有n個(gè)關(guān)鍵字的集合K=k1,k2, ,kn將其所有元素按完全二叉樹的順序存貯方式存于一個(gè)一維數(shù)組中，并且滿足以下條件，則該集合稱為最小堆（或最大堆）。nkik2i和kik2i+1 或 kik2i和kik2i+1 n( 其中，i = 1,2, (n 1)

3、/ 2 )091765234578875331123456789堆頂元素值最小堆頂元素值最小877853456509311723123456789堆頂元素值最大堆頂元素值最大09 17 65 23 45 78 87 53 31 1 2 3 4 5 6 7 8 9最小堆最小堆087 78 53 45 65 09 31 17 23 1 2 3 4 5 6 7 8 9最大堆最大堆072.二叉堆二叉堆n高為高為h的完全二叉樹有的完全二叉樹有2h到到2h+1-1個(gè)節(jié)點(diǎn)，個(gè)節(jié)點(diǎn)，完全二叉樹的高為完全二叉樹的高為O(logN)n完全二叉樹的數(shù)組存儲(chǔ)完全二叉樹的數(shù)組存儲(chǔ)09176523457887533112

4、3456789堆頂元素值最小堆頂元素值最小09 17 65 23 45 78 87 53 31 1 2 3 4 5 6 7 8 9最小堆最小堆082.二叉堆二叉堆nADTn假設(shè)關(guān)鍵字越小，優(yōu)先級(jí)越高假設(shè)關(guān)鍵字越小，優(yōu)先級(jí)越高n初始化初始化92.二叉堆二叉堆n插入（插入（insert）(上濾上濾)n新元素插到堆的后面，這樣可能破壞了堆序性。n為恢復(fù)堆序性，從插入元素雙親開始逐層向上篩選。091765234578875331123456789(a)篩選示意圖1110091165231778875331(b)篩選后45102.二叉堆二叉堆nDeleteminn即刪除堆頂元素，數(shù)組中即刪除堆頂元素，數(shù)

5、組中1號(hào)位置元素號(hào)位置元素n刪除操作破壞了完全二叉樹結(jié)構(gòu)刪除操作破壞了完全二叉樹結(jié)構(gòu)n下濾下濾n見圖見圖6-9到到6-11。112.二叉堆二叉堆nDecreaseKeyn減少關(guān)鍵字的值減少關(guān)鍵字的值提高優(yōu)先級(jí)提高優(yōu)先級(jí)n上濾上濾n任務(wù)管理器中的進(jìn)程管理任務(wù)管理器中的進(jìn)程管理nDecreaseKeyn增大關(guān)鍵字的值增大關(guān)鍵字的值降低優(yōu)先級(jí)降低優(yōu)先級(jí)n下濾下濾nDeleten首先首先decreasekey，然后，然后deleteminn進(jìn)程被終止進(jìn)程被終止122.二叉堆二叉堆nBuildheap（構(gòu)建堆）（構(gòu)建堆）n1.自上而下構(gòu)建自上而下構(gòu)建n依次插入每個(gè)元素，總保證堆序性依次插入每個(gè)元素，總保

6、證堆序性n2.自下而上構(gòu)建自下而上構(gòu)建nN個(gè)元素不考慮堆序性，直接存儲(chǔ)到一個(gè)完全個(gè)元素不考慮堆序性，直接存儲(chǔ)到一個(gè)完全二叉樹中；二叉樹中；n從第從第N/2個(gè)元素到第一個(gè)元素依次使用下濾，個(gè)元素到第一個(gè)元素依次使用下濾，就得到一個(gè)堆。就得到一個(gè)堆。132.二叉堆二叉堆n自上而下構(gòu)建堆自上而下構(gòu)建堆 50 1 root 0 1 2 3 4 5 6 7 501662 2478877數(shù)組數(shù)組 h 16 2142.二叉堆二叉堆n自上而下構(gòu)建堆自上而下構(gòu)建堆 16 1 root 0 1 2 3 4 5 6 7 165062 2478877數(shù)組數(shù)組 h50 2152.二叉堆二叉堆n自上而下構(gòu)建堆自上而下構(gòu)建

7、堆 16 1 root 0 1 2 3 4 5 6 7 165062 2478877數(shù)組數(shù)組 h50 262 3162.二叉堆二叉堆n自上而下構(gòu)建堆自上而下構(gòu)建堆16 1 root 0 1 2 3 4 5 6 7 165062 2478877數(shù)組數(shù)組 h50 224 4 62 3172.二叉堆二叉堆n自上而下構(gòu)建堆自上而下構(gòu)建堆 16 1 root 0 1 2 3 4 5 6 7 162462 5078877數(shù)組數(shù)組 h24 262 350 4 182.二叉堆二叉堆n自上而下構(gòu)建堆自上而下構(gòu)建堆 16 1 root 0 1 2 3 4 5 6 7 162462 5078877數(shù)組數(shù)組 h24

8、262 350 4 7 5192.二叉堆二叉堆n自上而下構(gòu)建堆自上而下構(gòu)建堆 16 1 root 0 1 2 3 4 5 6 7 16762 50248877數(shù)組數(shù)組 h7 262 350 4 24 5202.二叉堆二叉堆n自上而下構(gòu)建堆自上而下構(gòu)建堆 7 1 root 0 1 2 3 4 5 6 7 71662 50248877數(shù)組數(shù)組 h16 262 350 4 24 5212.二叉堆二叉堆n自上而下構(gòu)建堆自上而下構(gòu)建堆 7 1 root 0 1 2 3 4 5 6 7 71662 50248877數(shù)組數(shù)組 h16 262 350 4 24 5 88 6222.二叉堆二叉堆n自上而下構(gòu)建堆

9、自上而下構(gòu)建堆 7 1 root 0 1 2 3 4 5 6 7 71662 50248877數(shù)組數(shù)組 h16 262 350 4 24 5 88 677 723log(n!) = logj logx dx上述積分值為：上述積分值為：( (n+1)log(n+1)-(n+1)loge + 2loge - 2 ；它是它是O ( n logn ) 的。的。2.二叉堆二叉堆n自上而下構(gòu)建堆時(shí)間復(fù)雜度自上而下構(gòu)建堆時(shí)間復(fù)雜度n最大比較次數(shù)：最大比較次數(shù)：log2+log3+log(n-1)+logn求求 y=logx 的積分的示意圖的積分的示意圖j=2nn+12X軸軸Y軸軸2234y=logn1nn+

10、11242.二叉堆二叉堆n2.自下而上構(gòu)建自下而上構(gòu)建 50 1 16 224 4 7 562 3 88 677 7 root 0 1 2 3 4 5 6 7 501662 2478877葉子結(jié)點(diǎn)，符合堆的的定義葉子結(jié)點(diǎn)，符合堆的的定義。符合堆的定義，不需調(diào)整。即最小符合堆的定義，不需調(diào)整。即最小化小堆已符合定義?；《岩逊隙x。建立的第一個(gè)建立的第一個(gè)小堆的堆頂?shù)南聵?biāo)為小堆的堆頂?shù)南聵?biāo)為 n/2數(shù)組數(shù)組 h252.二叉堆二叉堆n2.自下而上構(gòu)建自下而上構(gòu)建 50 1 16 224 4 7 562 3 88 677 7 root 0 1 2 3 4 5 6 7 501662 2478877不

11、合堆的定義，需調(diào)整。建立不合堆的定義，需調(diào)整。建立以以 L 2 為堆頂?shù)恼_的最小為堆頂?shù)恼_的最小化小堆。化小堆。數(shù)組數(shù)組 h262.二叉堆二叉堆n2.自下而上構(gòu)建自下而上構(gòu)建 50 1 7 224 4 16 562 3 88 677 7 root 0 1 2 3 4 5 6 7 50762 24168877不合堆的定義，需調(diào)整。建立不合堆的定義，需調(diào)整。建立以以 L 2 為堆頂?shù)恼_的最小為堆頂?shù)恼_的最小化小堆。化小堆。數(shù)組數(shù)組 h272.二叉堆二叉堆n2.自下而上構(gòu)建自下而上構(gòu)建 50 17 224 4 16 562 3 88 677 7 root 0 1 2 3 4 5 6 7 50

12、762 24168877數(shù)組數(shù)組 h不合堆的定義，需調(diào)整。不合堆的定義，需調(diào)整。建立以建立以 L 1 為堆頂?shù)恼秊槎秧數(shù)恼_的最小化堆確的最小化堆。282.二叉堆二叉堆n2.自下而上構(gòu)建自下而上構(gòu)建 7 150 224 4 16 562 3 88 677 7 root 0 1 2 3 4 5 6 7 75062 24168877數(shù)組數(shù)組 h不合堆的定義，需調(diào)整。不合堆的定義，需調(diào)整。建立以建立以 L 1 為堆頂?shù)恼秊槎秧數(shù)恼_的最小化堆確的最小化堆。292.二叉堆二叉堆n2.自下而上構(gòu)建自下而上構(gòu)建 7 116 224 4 50 562 3 88 677 7 root 0 1 2 3 4 5

13、6 7 71662 24508877數(shù)組數(shù)組 h不合堆的定義，需調(diào)整。不合堆的定義，需調(diào)整。建立以建立以 L 1 為堆頂?shù)恼秊槎秧數(shù)恼_的最小化堆確的最小化堆。302.二叉堆二叉堆n2.自下而上構(gòu)建自下而上構(gòu)建n時(shí)間復(fù)雜度分析時(shí)間復(fù)雜度分析n時(shí)間復(fù)雜度是所有節(jié)點(diǎn)高度之和時(shí)間復(fù)雜度是所有節(jié)點(diǎn)高度之和n定理：包含定理：包含2b+1-1個(gè)節(jié)點(diǎn)高為個(gè)節(jié)點(diǎn)高為b的理想二叉樹的理想二叉樹的節(jié)點(diǎn)的高度的和為的節(jié)點(diǎn)的高度的和為2b+1-1-(b+1).n而而2b=N=NPL(右子樹右子樹)n根的零路徑長根的零路徑長= NPL(右子樹右子樹)+1n迭代迭代n故根的零路徑長對(duì)應(yīng)的是右路徑故根的零路徑長對(duì)應(yīng)的是右路

14、徑385.左式堆左式堆12211rriin定理：定理：n右路徑有右路徑有r個(gè)節(jié)點(diǎn)的左式樹至少有個(gè)節(jié)點(diǎn)的左式樹至少有2r-1個(gè)個(gè)節(jié)點(diǎn)節(jié)點(diǎn)紅色各層相加紅色各層相加nN個(gè)節(jié)點(diǎn)的左式樹右路徑最多有個(gè)節(jié)點(diǎn)的左式樹右路徑最多有l(wèi)og(N+1)個(gè)節(jié)點(diǎn)（上述定理求解即可）個(gè)節(jié)點(diǎn)（上述定理求解即可） r層層395.左式堆左式堆n基本操作：合并基本操作：合并n適合合并適合合并n簡單易操作簡單易操作n合并：合并：n互相遞歸與右子樹合并互相遞歸與右子樹合并n堆序性：大堆序性：大key節(jié)點(diǎn)與小節(jié)點(diǎn)與小key節(jié)點(diǎn)右子樹合并節(jié)點(diǎn)右子樹合并n左偏性：不滿足時(shí)，交換左右子樹左偏性：不滿足時(shí)，交換左右子樹n實(shí)例見圖實(shí)例見圖6-2

15、1405.左式堆左式堆nADTn合并合并415.左式堆左式堆n合并的非遞歸方法合并的非遞歸方法n第一趟第一趟n按照按照key大小重新排列需合并的兩個(gè)左式堆的大小重新排列需合并的兩個(gè)左式堆的右路徑上的節(jié)點(diǎn)，形成一個(gè)新的右路徑。右路徑上的節(jié)點(diǎn)，形成一個(gè)新的右路徑。n保持各節(jié)點(diǎn)左子樹不變。保持各節(jié)點(diǎn)左子樹不變。n形成了一個(gè)新的樹。形成了一個(gè)新的樹。n第二趟第二趟n在左偏性遭到破壞的節(jié)點(diǎn)，交換其左右子樹，在左偏性遭到破壞的節(jié)點(diǎn)，交換其左右子樹，恢復(fù)左偏性?；謴?fù)左偏性。425.左式堆左式堆n插入插入n=合并（一個(gè)左式堆合并（一個(gè)左式堆+僅一個(gè)元素的左式堆）僅一個(gè)元素的左式堆）nDeleteminn=合并

16、（原根左子樹合并（原根左子樹+原根右子樹）原根右子樹）436.斜堆斜堆n去掉左偏性質(zhì)的左式堆去掉左偏性質(zhì)的左式堆n合并操作與左式堆比較合并操作與左式堆比較n相同點(diǎn)：相同點(diǎn)：n遞歸與右子樹合并遞歸與右子樹合并n按照堆序性合并按照堆序性合并n不同點(diǎn)：不同點(diǎn)：n不考慮左偏性不考慮左偏性n一律交換左右子樹一律交換左右子樹見圖見圖6-32447.二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列n定義：定義：n是一組具有堆序性和結(jié)構(gòu)性約束的樹的集合是一組具有堆序性和結(jié)構(gòu)性約束的樹的集合n相鄰二項(xiàng)樹關(guān)系相鄰二項(xiàng)樹關(guān)系n同一二項(xiàng)樹不同層次節(jié)點(diǎn)個(gè)數(shù)的關(guān)系同一二項(xiàng)樹不同層次節(jié)點(diǎn)個(gè)數(shù)的關(guān)系457.二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列n高度為高度為k的二項(xiàng)樹的二項(xiàng)樹B

17、k定義為：定義為：n若若k = 0，則該樹只有一個(gè)結(jié)點(diǎn)；，則該樹只有一個(gè)結(jié)點(diǎn)；n若若k 0，則該樹的根是高度為，則該樹的根是高度為k的結(jié)點(diǎn)，其的結(jié)點(diǎn)，其子樹為子樹為B0，B1，Bk-1。nBk在二項(xiàng)隊(duì)列中具有唯一性在二項(xiàng)隊(duì)列中具有唯一性467.二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列n二項(xiàng)樹二項(xiàng)樹Bk具有具有2k個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。n證明：證明：n對(duì)對(duì)k應(yīng)用歸納法。應(yīng)用歸納法。n當(dāng)當(dāng)k = 0，顯然成立。，顯然成立。n假設(shè)假設(shè)k m時(shí)成立。則當(dāng)時(shí)成立。則當(dāng)k = m時(shí)，該樹共有時(shí)，該樹共有1 + 20 + 21 + ，+ 2m-1 = 2m 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。n命題得證。命題得證。n二項(xiàng)樹二項(xiàng)樹Bk深度深度d處的節(jié)點(diǎn)總數(shù)為二項(xiàng)系數(shù)處的節(jié)點(diǎn)總數(shù)為二項(xiàng)系數(shù)n證明略證明略dk477.二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列n左兒子左兒子-兄弟表示法兄弟表示法n實(shí)現(xiàn)見圖實(shí)現(xiàn)見圖6-51nA