湘潭大學(xué)數(shù)據(jù)結(jié)構(gòu)課件pptCh06PriorityQueues(Heaps)

1、Review隊(duì)列先進(jìn)先出設(shè)想：發(fā)送到打印機(jī)的文檔放到隊(duì)列中，如果希望先打印重要的或短的文檔？操作系統(tǒng)調(diào)度程序使用隊(duì)列，重要的或短的作業(yè)能優(yōu)先嗎？第六章 優(yōu)先隊(duì)列（堆） 刪除具有最高刪除具有最高/ /最低優(yōu)先級(jí)的元素最低優(yōu)先級(jí)的元素1 ADT 模型模型數(shù)據(jù)對(duì)象集數(shù)據(jù)對(duì)象集: 一個(gè)有限的有序表，包含零個(gè)或多個(gè)元素。一個(gè)有限的有序表，包含零個(gè)或多個(gè)元素。數(shù)據(jù)操作集數(shù)據(jù)操作集: PriorityQueue Initialize( int MaxElements ); void Insert( ElementType X, PriorityQueue H ); ElementType DeleteMin

2、( PriorityQueue H ); ElementType FindMin( PriorityQueue H ); 【定義定義】 “優(yōu)先隊(duì)列優(yōu)先隊(duì)列” （Priority Queue）是特殊的）是特殊的“隊(duì)列隊(duì)列”，從堆中，從堆中取出元素的順序是依照元素的取出元素的順序是依照元素的優(yōu)先權(quán)（關(guān)鍵字）優(yōu)先權(quán)（關(guān)鍵字）大小，而不是元素進(jìn)入大小，而不是元素進(jìn)入隊(duì)列的先后順序。采用完全二叉樹存儲(chǔ)的優(yōu)先隊(duì)列隊(duì)列的先后順序。采用完全二叉樹存儲(chǔ)的優(yōu)先隊(duì)列 稱為稱為堆堆（Heap）。）。2 簡單的實(shí)現(xiàn)簡單的實(shí)現(xiàn) 數(shù)組數(shù)組 :Insertion 元素插入在末尾元素插入在末尾 ( 1 )Deletion 查找

3、最大（或最小）關(guān)鍵字查找最大（或最?。╆P(guān)鍵字 ( n ) 從數(shù)組中刪除需要移動(dòng)元素從數(shù)組中刪除需要移動(dòng)元素 O( n ) 鏈表鏈表:Insertion 元素總是插入鏈表的頭部元素總是插入鏈表的頭部 ( 1 )Deletion 查找最大（或最?。╆P(guān)鍵字查找最大（或最?。╆P(guān)鍵字 ( n ) 刪去結(jié)點(diǎn)刪去結(jié)點(diǎn) ( 1 ) 有序數(shù)組有序數(shù)組:Insertion 找到合適的位置找到合適的位置 O( n )或或O(logn) 移動(dòng)元素并插入移動(dòng)元素并插入 O( n )Deletion 刪去最后一個(gè)元素刪去最后一個(gè)元素 ( 1 ) 有序鏈表有序鏈表:Insertion 找到合適的位置找到合適的位置 O( n

4、 ) 插入元素插入元素 ( 1 )Deletion 刪除首元素或最后元素刪除首元素或最后元素 ( 1 )由于由于Deletion的次數(shù)從不多余的次數(shù)從不多余Insertion的次數(shù)，鏈表可能是的次數(shù)，鏈表可能是更好的想法。更好的想法。 二叉查找樹二叉查找樹:2 簡單的實(shí)現(xiàn)簡單的實(shí)現(xiàn)其實(shí)其實(shí)AVL 的許多操作的許多操作對(duì)優(yōu)先隊(duì)列而言并不是必須的對(duì)優(yōu)先隊(duì)列而言并不是必須的.而且而且, 指針操作總帶有某些潛在的危險(xiǎn)指針操作總帶有某些潛在的危險(xiǎn) 好好! 好注意好注意! 插入和刪除都只需要插入和刪除都只需要O(log N) .可是要注意可是要注意-插入是隨機(jī)的插入是隨機(jī)的, 而刪除不是。而刪除不是。 我

5、們總是假定刪除最大的元素我們總是假定刪除最大的元素. 呃哦呃哦 還不行嗎還不行嗎? 哦哦, 對(duì)呀對(duì)呀, 我們總是從左子樹刪除我們總是從左子樹刪除.而我們還必須保持樹的平衡而我們還必須保持樹的平衡 我想你是不是又有更好的想法了我想你是不是又有更好的想法了?現(xiàn)在你開始懂現(xiàn)在你開始懂 我了我了 你越來越聰明啦你越來越聰明啦! 像像AVL 樹這種平衡二叉樹并不一定是樹這種平衡二叉樹并不一定是個(gè)壞主意，因?yàn)槲覀冎恍枰黾映?shù)的個(gè)壞主意，因?yàn)槲覀冎恍枰黾映?shù)的運(yùn)行時(shí)間?？墒沁\(yùn)行時(shí)間?？墒?3 二叉堆二叉堆1. 結(jié)構(gòu)性質(zhì)結(jié)構(gòu)性質(zhì):【定義定義】一棵具有一棵具有 n 個(gè)結(jié)點(diǎn)，高度為個(gè)結(jié)點(diǎn)，高度為 h 的二叉樹

6、是的二叉樹是完全二完全二叉樹叉樹，當(dāng)且僅當(dāng)它的結(jié)點(diǎn)編號(hào)與高度為，當(dāng)且僅當(dāng)它的結(jié)點(diǎn)編號(hào)與高度為 h 的滿二叉樹結(jié)點(diǎn)的滿二叉樹結(jié)點(diǎn)編號(hào)能一一對(duì)應(yīng)。編號(hào)能一一對(duì)應(yīng)。489510116121371415231一棵一棵高度為高度為 h 的完全二叉樹結(jié)點(diǎn)數(shù)為的完全二叉樹結(jié)點(diǎn)數(shù)為至至個(gè)。個(gè)。2h2h+1 1h = log N 數(shù)組實(shí)現(xiàn)數(shù)組實(shí)現(xiàn): BT n + 1 ( BT 0 未使用未使用)DHIEJFGBCABT01A2B3C4D5E6F7G8H9I10J1112133 二叉堆二叉堆【引理引理】如果一棵具有如果一棵具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹是順序?qū)崿F(xiàn)個(gè)結(jié)點(diǎn)的完全二叉樹是順序?qū)崿F(xiàn)的，那么對(duì)任意位置編號(hào)的，

7、那么對(duì)任意位置編號(hào) i 的的結(jié)點(diǎn)，結(jié)點(diǎn)， 1 i n，有：有： niniiichildrightniniiichildleftiiiiparent12 ifNone12 if12)(_ ofindex (3)2 ifNone2 if2)(_ ofindex (2)1 ifNone1 if2)( ofindex (1)3 二叉堆二叉堆PriorityQueue Initialize( int MaxElements ) PriorityQueue H; if ( MaxElements Elements = malloc( MaxElements + 1 ) * sizeof( ElementT

8、ype ); if ( H-Elements = NULL ) return FatalError( Out of space! ); H-Capacity = MaxElements; H-Size = 0; H-Elements 0 = MinData; /* set the sentinel */ return H; 3 二叉堆二叉堆2. 堆序性質(zhì)堆序性質(zhì):【定義定義】一棵一棵最小樹最小樹是樹中任意結(jié)點(diǎn)的關(guān)鍵字不大于它是樹中任意結(jié)點(diǎn)的關(guān)鍵字不大于它的孩子結(jié)點(diǎn)的關(guān)鍵字（如果有的話）。一個(gè)的孩子結(jié)點(diǎn)的關(guān)鍵字（如果有的話）。一個(gè)最小堆最小堆是是一棵一棵完全二叉樹完全二叉樹，同時(shí)也是一棵，同時(shí)也

9、是一棵最小樹最小樹。Note: 類似地，我們可以聲明一個(gè)類似地，我們可以聲明一個(gè)最大堆最大堆，只要更改，只要更改堆序性質(zhì)即可。堆序性質(zhì)即可。96531234一個(gè)最大堆一個(gè)最大堆102050831234一個(gè)最小堆一個(gè)最小堆最大關(guān)鍵字最大關(guān)鍵字最小關(guān)鍵字最小關(guān)鍵字3 二叉堆二叉堆3. 基本的堆操作基本的堆操作: insertion1012152012341856 算法梗概算法梗概:由于堆必須是完全二叉樹，由于堆必須是完全二叉樹，這是唯一可能插入這是唯一可能插入新結(jié)點(diǎn)的位置。新結(jié)點(diǎn)的位置。情形情形 1 : new_item = 212120211720101791099103 二叉堆二叉堆/* H-

10、Element 0 is a sentinel */ void Insert( ElementType X, PriorityQueue H ) int i; if ( IsFull( H ) ) Error( Priority queue is full ); return; for ( i = +H-Size; H-Elements i / 2 X; i /= 2 ) H-Elements i = H-Elements i / 2 ; H-Elements i = X; 上濾上濾Percolate up比比swap快快H-Element 0 是一個(gè)是一個(gè)哨兵哨兵 ，即比堆中最小的值，即比堆

11、中最小的值還要小。還要小。T (N) = O ( log N )3 二叉堆二叉堆 DeleteMin 算法梗概算法梗概:101215201234185 move 18 up to the root18 find the smaller child of 18121818121518Elements 0 ; MinElement = H-Elements 1 ; /* save the min element */ LastElement = H-Elements H-Size- ; /* take last and reset size */ for ( i = 1; i * 2 Size;

12、i = Child ) /* Find smaller child */ Child = i * 2; if (Child != H-Size & H-ElementsChild+1 ElementsChild) Child+; if ( LastElement H-Elements Child ) /* Percolate one level */ H-Elements i = H-Elements Child ; else break; /* find the proper position */ H-Elements i = LastElement; return MinElem

13、ent; 下濾下濾Percolate down省略這個(gè)條件，省略這個(gè)條件，會(huì)發(fā)生什么？會(huì)發(fā)生什么？通過添加另一個(gè)通過添加另一個(gè)哨兵，能否去掉哨兵，能否去掉這個(gè)測試這個(gè)測試?3 二叉堆二叉堆4. 其他的堆操作其他的堆操作:Note: 查找除最小元外的任何元素都需對(duì)整個(gè)堆進(jìn)行線查找除最小元外的任何元素都需對(duì)整個(gè)堆進(jìn)行線性搜索。性搜索。 DecreaseKey ( P, , H )將堆將堆 H 中位置中位置 P 處的結(jié)點(diǎn)關(guān)鍵字減小處的結(jié)點(diǎn)關(guān)鍵字減小 因此我的程序可以以更高優(yōu)先級(jí)運(yùn)行因此我的程序可以以更高優(yōu)先級(jí)運(yùn)行 .sys. admin. IncreaseKey ( P, , H )Percolat

14、e upsys. admin.將堆將堆 H 中位置中位置 P 處的結(jié)點(diǎn)關(guān)鍵字增加處的結(jié)點(diǎn)關(guān)鍵字增加 將過度消耗將過度消耗CPU時(shí)間的進(jìn)程降低優(yōu)先級(jí)。時(shí)間的進(jìn)程降低優(yōu)先級(jí)。Percolate down3 二叉堆二叉堆 Delete ( P, H )將堆將堆 H 中位置中位置 P 處的結(jié)點(diǎn)刪除處的結(jié)點(diǎn)刪除 當(dāng)一個(gè)進(jìn)程當(dāng)一個(gè)進(jìn)程由用戶中止（非正常終止）時(shí)，它必須從優(yōu)先由用戶中止（非正常終止）時(shí)，它必須從優(yōu)先隊(duì)列中除去。隊(duì)列中除去。sys. admin.DecreaseKey(P, , H); DeleteMin(H) BuildHeap ( H )將將 N 個(gè)關(guān)鍵字以任意順序放到一個(gè)空堆個(gè)關(guān)鍵字以任

15、意順序放到一個(gè)空堆H中中。sys. admin.N successive Insertions ? 那太。慢了那太。慢了!301002010906070501201101401308040150150, 80, 40, 30, 10, 70, 110, 100, 20, 90, 60, 50, 120, 140, 130PercolateDown (7)PercolateDown (6)5070PercolateDown (5)PercolateDown (4)2030PercolateDown (3)PercolateDown (2)80108060PercolateDown (1)1501

16、01502015030T (N) = ?3 二叉堆二叉堆【定理定理】對(duì)高度為對(duì)高度為 h ，包含，包含 2h+1 1 個(gè)結(jié)點(diǎn)的滿二叉樹，結(jié)個(gè)結(jié)點(diǎn)的滿二叉樹，結(jié)點(diǎn)高度之和為點(diǎn)高度之和為 2h+1 1 (h + 1).T ( N ) = O ( N )4 優(yōu)先隊(duì)列的應(yīng)用優(yōu)先隊(duì)列的應(yīng)用例例1選擇問題：已知一個(gè)有選擇問題：已知一個(gè)有N個(gè)元素的表，給定一個(gè)整個(gè)元素的表，給定一個(gè)整數(shù)數(shù)k，找到表中第，找到表中第k大的元素。大的元素。你能想到幾種方法來解決這個(gè)問題？你能想到幾種方法來解決這個(gè)問題？它們各自的時(shí)間復(fù)雜度是多少？它們各自的時(shí)間復(fù)雜度是多少？5 d-堆堆- 所有的結(jié)點(diǎn)都有所有的結(jié)點(diǎn)都有 d 個(gè)孩子

17、個(gè)孩子315136517892741091113-heapQuestion: d 是否越大越好是否越大越好?Note: 1. DeleteMin 將需要進(jìn)行將需要進(jìn)行 d 1 次比較來找出最小的孩子。因次比較來找出最小的孩子。因此總的時(shí)間復(fù)雜度將會(huì)提高到此總的時(shí)間復(fù)雜度將會(huì)提高到 O(d logd N). 2.*2 或或 /2 僅僅需要一次僅僅需要一次移位移位，但，但 *d 和和 /d 不能通過移位實(shí)現(xiàn)不能通過移位實(shí)現(xiàn)。 3. 當(dāng)優(yōu)先隊(duì)列太大不能完全裝入主存的時(shí)候，當(dāng)優(yōu)先隊(duì)列太大不能完全裝入主存的時(shí)候，d-堆是很有用的。堆是很有用的。4. 在實(shí)踐中在實(shí)踐中4-堆可以勝過二叉堆。堆可以勝過二叉堆

18、。6 左式堆左式堆 Heap: 結(jié)構(gòu)性質(zhì)結(jié)構(gòu)性質(zhì) + 堆序性質(zhì)堆序性質(zhì)Target : 加速合并操作。加速合并操作。 必須把一個(gè)數(shù)組拷貝到另一個(gè)數(shù)組中去必須把一個(gè)數(shù)組拷貝到另一個(gè)數(shù)組中去 (N) 使用使用指針指針 使所有其他的操作變慢使所有其他的操作變慢左式堆左式堆: 堆序性質(zhì)堆序性質(zhì) 不變不變 結(jié)構(gòu)性質(zhì)結(jié)構(gòu)性質(zhì) 二叉樹，且趨向于非常二叉樹，且趨向于非常不平衡不平衡6 左式堆左式堆【定義定義】任意節(jié)點(diǎn)任意節(jié)點(diǎn)X的的零路徑長零路徑長, Npl(X) 是從是從X到一個(gè)沒有兩個(gè)兒子到一個(gè)沒有兩個(gè)兒子的結(jié)點(diǎn)的最短路徑的長。的結(jié)點(diǎn)的最短路徑的長。Npl(NULL) = 1.Note: Npl(X) =

19、min Npl(C) + 1 for all C as children of X 【定義定義】左式堆性質(zhì)左式堆性質(zhì)是：對(duì)堆中的每一個(gè)結(jié)點(diǎn)是：對(duì)堆中的每一個(gè)結(jié)點(diǎn)X，左兒子左兒子的零路徑的零路徑長長至少至少與與右兒子右兒子的零路徑長的零路徑長一樣大一樣大。000101 0010101 偏重于使樹偏重于使樹向左向左增增加深度。加深度。6 左式堆左式堆【定理定理】在右路徑上有在右路徑上有 r 個(gè)結(jié)點(diǎn)的左式樹必然至少有個(gè)結(jié)點(diǎn)的左式樹必然至少有 2r 1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。證明證明: 數(shù)學(xué)歸納法，數(shù)學(xué)歸納法，p. 146.Note: N 個(gè)結(jié)點(diǎn)的左式樹有一條右路徑最多包含個(gè)結(jié)點(diǎn)的左式樹有一條右路徑最多包含

20、 log(N+1) 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 所有的工作在所有的工作在右路徑右路徑上進(jìn)行，保證樹深較上進(jìn)行，保證樹深較短短。Trouble makers: Insert 和和 MergeNote: Insertion 只是只是 merge 的特殊情形。的特殊情形。6 左式堆左式堆struct TreeNode ElementType Element;PriorityQueue Left;PriorityQueue Right;int Npl; ; 聲明聲明: Merge (遞歸實(shí)現(xiàn)遞歸實(shí)現(xiàn)): 3102114238172661218243373718H1H2Step 1: Merge( H1-Righ

21、t, H2 )8172661218243371837Step 2: Attach( H2, H1-Right )3102114238172661218243371837Step 3: 必要的話，必要的話，Swap(H1-Right, H1-Left ) 6 左式堆左式堆PriorityQueue Merge ( PriorityQueue H1, PriorityQueue H2 ) if ( H1 = NULL ) return H2;if ( H2 = NULL ) return H1;if ( H1-Element Element ) return Merge1( H1, H2 );el

22、se return Merge1( H2, H1 );static PriorityQueueMerge1( PriorityQueue H1, PriorityQueue H2 ) if ( H1-Left = NULL ) /* single node */H1-Left = H2;/* H1-Right is already NULL and H1-Npl is already 0 */else H1-Right = Merge( H1-Right, H2 ); /* Step 1 & 2 */if ( H1-Left-Npl Right-Npl )SwapChildren( H

23、1 );/* Step 3 */H1-Npl = H1-Right-Npl + 1; /* end else */return H1;如果如果Npl 沒有更新沒有更新會(huì)怎樣呢？會(huì)怎樣呢？Tp = O(log N)6 左式堆左式堆 Merge (非遞歸實(shí)現(xiàn)非遞歸實(shí)現(xiàn)): 3102114238172661218243373718H1H2Step 1: 對(duì)右路徑上的結(jié)點(diǎn)排序，并保對(duì)右路徑上的結(jié)點(diǎn)排序，并保持他們的左兒子不變。持他們的左兒子不變。3102114236121824337371881726Step 2: 必要時(shí)交換結(jié)點(diǎn)左右子樹。必要時(shí)交換結(jié)點(diǎn)左右子樹。3102114236121824337

24、371881726 DeleteMin: p.150. Step 1: 刪除根刪除根Step 2: Merge兩棵子樹兩棵子樹Tp = O(log N)7 斜堆斜堆- 左式堆的簡單版本左式堆的簡單版本Target : 任意任意 M 次連續(xù)操作最多花費(fèi)次連續(xù)操作最多花費(fèi) O(M log N) 時(shí)間。時(shí)間。 Merge: 總是總是交換左右孩子，除了右路徑上交換左右孩子，除了右路徑上最大的結(jié)點(diǎn)最大的結(jié)點(diǎn)外。不考慮外。不考慮 Npl。3102114238172661218243373718H1H23102114236121824337372681718并不是特殊情形，而并不是特殊情形，而是自然遞歸實(shí)現(xiàn)

25、時(shí)的是自然遞歸實(shí)現(xiàn)時(shí)的終止。終止。31021142361218243318737268177 斜堆斜堆【例例2】Insert 1515102136121824331873726817142315 Merge (非遞歸實(shí)現(xiàn)非遞歸實(shí)現(xiàn)): 3102114238172661218243373718H1H231021142361218243373726817187 斜堆斜堆Note: 斜堆的優(yōu)點(diǎn)是斜堆的優(yōu)點(diǎn)是不需要附加的空間不需要附加的空間來保留路徑長以及來保留路徑長以及不需要測試不需要測試確定何時(shí)交換孩子。確定何時(shí)交換孩子。 精確確定左式堆和斜堆的精確確定左式堆和斜堆的期望右路徑長期望右路徑長是一個(gè)

26、未解決的問題。是一個(gè)未解決的問題。常數(shù)常數(shù)! 所以一次插入花費(fèi)所以一次插入花費(fèi) O(log N) 時(shí)間并時(shí)間并不夠好不夠好！我們已經(jīng)有了足夠多的隊(duì)列了，我們已經(jīng)有了足夠多的隊(duì)列了，為什么要使用為什么要使用二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列？ O(log N) 有問題嗎有問題嗎? 根據(jù)定理根據(jù)定理 6.1 , 總的時(shí)間是總的時(shí)間是 O(N)插入插入 N 個(gè)關(guān)鍵字到個(gè)關(guān)鍵字到一個(gè)空的二叉堆，一個(gè)空的二叉堆，總共總共需要花費(fèi)多少時(shí)間？需要花費(fèi)多少時(shí)間？ 那么平均時(shí)間是？那么平均時(shí)間是？8 二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列 結(jié)構(gòu)結(jié)構(gòu): 一個(gè)二項(xiàng)隊(duì)列并非一個(gè)二項(xiàng)隊(duì)列并非一棵一棵堆序樹，而是堆序樹的堆序樹，而是堆序樹的集合集合，稱為，稱為

27、森林森林。每。每棵堆序樹是一棵棵堆序樹是一棵二項(xiàng)樹二項(xiàng)樹。高度為高度為 0 的二項(xiàng)樹是一棵單結(jié)點(diǎn)樹。的二項(xiàng)樹是一棵單結(jié)點(diǎn)樹。高度為高度為 k 的二項(xiàng)樹的二項(xiàng)樹Bk 通過將一棵二項(xiàng)樹通過將一棵二項(xiàng)樹 Bk 1 附接到另一棵二項(xiàng)樹附接到另一棵二項(xiàng)樹Bk 1的根上而構(gòu)成。的根上而構(gòu)成。B0B1B2B3 Bk 包含一個(gè)根和包含一個(gè)根和 個(gè)子樹個(gè)子樹, kB0, B1, , Bk 1 。Bk 恰好有恰好有 個(gè)結(jié)點(diǎn)。而深度個(gè)結(jié)點(diǎn)。而深度 d 處的結(jié)點(diǎn)數(shù)是處的結(jié)點(diǎn)數(shù)是 。2kkd二項(xiàng)系數(shù)二項(xiàng)系數(shù)在在左式堆左式堆和和斜堆斜堆中，中，插入的插入的平均時(shí)間平均時(shí)間是？是？8 二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列【例例3】用二項(xiàng)樹的集

28、合實(shí)現(xiàn)一個(gè)大小為用二項(xiàng)樹的集合實(shí)現(xiàn)一個(gè)大小為 13 的優(yōu)先隊(duì)列。的優(yōu)先隊(duì)列。Bk 結(jié)構(gòu)結(jié)構(gòu) + 堆序堆序 + 任意高度上最多有一棵二項(xiàng)樹任意高度上最多有一棵二項(xiàng)樹 用二項(xiàng)樹的集合用二項(xiàng)樹的集合唯一唯一地表示地表示任意大小任意大小的優(yōu)先隊(duì)列的優(yōu)先隊(duì)列方法方法:13 = 20 + 0 21 + 22 + 23 = 11012B0B1B2B3132351246512212465142616188 二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列 操作實(shí)現(xiàn)操作實(shí)現(xiàn): FindMin: 最小元是某一棵樹的最小元是某一棵樹的根根。最多有最多有 個(gè)根，因此個(gè)根，因此 Tp = O( ).log Nlog NNote: 如果我們記住最小元，

29、并在其他操作期間變化時(shí)更新它，那如果我們記住最小元，并在其他操作期間變化時(shí)更新它，那么可以么可以O(shè)(1)的時(shí)間執(zhí)行的時(shí)間執(zhí)行FindMin。 Merge: H1H213122124651618142623512465H11 1 0 2 = 6+ 1 1 1 2 = 71130c142616181c12212465235124651Tp = O( )log N必須將這些樹放在必須將這些樹放在按照按照高度排序高度排序的二項(xiàng)隊(duì)列中。的二項(xiàng)隊(duì)列中。8 二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列 Insert: Merge的特殊情形。的特殊情形。 【例例4】將將 1, 2, 3, 4, 5, 6, 7 插入到一個(gè)初始為空的隊(duì)列中

30、。插入到一個(gè)初始為空的隊(duì)列中。123412345657Note: 如果元素將要插入的那個(gè)優(yōu)先隊(duì)列中不存在的最小的二項(xiàng)樹是如果元素將要插入的那個(gè)優(yōu)先隊(duì)列中不存在的最小的二項(xiàng)樹是 Bi ，那么運(yùn)行時(shí)間，那么運(yùn)行時(shí)間Tp = Const (i + 1)。 在初始為空的二項(xiàng)隊(duì)列上進(jìn)行在初始為空的二項(xiàng)隊(duì)列上進(jìn)行 N 次次插入插入最多將花費(fèi)最多將花費(fèi) O(N) 時(shí)間。時(shí)間。因此因此平均平均時(shí)間是時(shí)間是常數(shù)常數(shù)。8 二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列 DeleteMin ( H ):H13142616181221246523512465H1314261618Step 1: FindMin in BkStep 2: Remov

31、e Bk from HStep 3: Remove root from Bk 21246523512465H”Step 4: Merge (H, H”)23512465H1321246514261618/* O(log N) */* O(1) */* O(log N) */* O(log N) */8 二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列 實(shí)現(xiàn)實(shí)現(xiàn): 二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列 = 二項(xiàng)樹的二項(xiàng)樹的數(shù)組數(shù)組DeleteMinMerge快速找到所有快速找到所有子樹子樹諸兒子按照大小諸兒子按照大小排序排序操作操作特征特征解決方法解決方法兒子兄弟表示法兒子兄弟表示法新的樹將是最大的一棵，新的樹將是最大的一棵，因此以因此以大小遞減

32、大小遞減方式保方式保持這些子樹。持這些子樹。1313142616181221246523512465H012341416261812242165232451658 二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列typedef struct BinNode *Position;typedef struct Collection *BinQueue;typedef struct BinNode *BinTree; /* missing from p.176 */struct BinNode ElementType Element;Position LeftChild;Position NextSibling; ;struct

33、Collection int CurrentSize; /* total number of nodes */BinTreeTheTrees MaxTrees ; ;8 二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列BinTreeCombineTrees( BinTree T1, BinTree T2 ) /* merge equal-sized T1 and T2 */if ( T1-Element T2-Element )/* attach the larger one to the smaller one */return CombineTrees( T2, T1 );/* insert T2 to the fron

34、t of the children list of T1 */T2-NextSibling = T1-LeftChild;T1-LeftChild = T2;return T1;Tp = O( 1 )1224216514162618T1T28 二項(xiàng)隊(duì)列二項(xiàng)隊(duì)列BinQueue Merge( BinQueue H1, BinQueue H2 )BinTree T1, T2, Carry = NULL; int i, j;if ( H1-CurrentSize + H2- CurrentSize Capacity ) ErrorMessage();H1-CurrentSize += H2- Cur

35、rentSize;for ( i=0, j=1; jCurrentSize; i+, j*=2 ) T1 = H1-TheTreesi; T2 = H2-TheTreesi; /*current trees */ switch( 4*!Carry + 2*!T2 + !T1 ) /* assign each digit to a tree */case 0: /* 000 */ case 1: /* 001 */ break;case 2: /* 010 */ H1-TheTreesi = T2; H2-TheTreesi = NULL; break;case 4: /* 100 */ H1-TheTreesi = Carry; Carry = NULL; break;case 3: /* 011 */ Carry = CombineTrees( T1, T2 ); H1-TheTreesi = H2-TheTreesi = NULL; break;case 5: /* 101 */ Carry = CombineTrees( T1, Carry ); H1-TheTreesi = NULL; break;case 6: /* 110 */ Carry