1、教學重點教學重點減治法的設計思想，各種經典問題的減治思想減治法的設計思想，各種經典問題的減治思想教學難點教學難點二叉查找樹，堆排序二叉查找樹，堆排序教學內容教學內容及目標及目標知識點知識點教學要求教學要求了解了解理解理解掌握掌握熟練掌握熟練掌握減治法的設計思想減治法的設計思想折半查找折半查找二叉查找樹二叉查找樹選擇問題選擇問題插入排序插入排序堆排序堆排序淘汰賽冠軍問題淘汰賽冠軍問題假幣問題假幣問題學習目標學習目標第第5章章 減治法減治法 5.1 概述概述 5.2 查找問題中的減治法查找問題中的減治法5.3 排序問題中的減治法排序問題中的減治法5.4 組合問題中的減治法組合問題中的減治法閱讀材料

2、閱讀材料 假幣問題的復雜版本假幣問題的復雜版本5.1 概述概述 分治法：把一個大問題劃分為若干個子問題，分別求分治法：把一個大問題劃分為若干個子問題，分別求解各個子問題，然后將子問題的解合并得到解各個子問題，然后將子問題的解合并得到原問題的解。原問題的解。減治法：同樣把一個大問題劃分為若干個子問題，但減治法：同樣把一個大問題劃分為若干個子問題，但無須分別求解這些子問題，只需求解其中的無須分別求解這些子問題，只需求解其中的一個子問題，因而無需對子問題的解進行合一個子問題，因而無需對子問題的解進行合并。退化了的分治法。并。退化了的分治法。減治法的設計思想減治法的設計思想 減治法將問題劃分為若干子問

3、題，并且規模為減治法將問題劃分為若干子問題，并且規模為n的的原問題的解與較小規模（通常是原問題的解與較小規模（通常是n/2）的子問題的解之）的子問題的解之間具有某種確定的關系：間具有某種確定的關系：（1）原問題的解只存在于其中一個較小規模的子問題中；原問題的解只存在于其中一個較小規模的子問題中；（2）原問題的解與其中一個較小規模的解之間有某種對應關系。原問題的解與其中一個較小規模的解之間有某種對應關系。 由于原問題的解與較小規模的子問題的解之間存在由于原問題的解與較小規模的子問題的解之間存在這種關系，所以，這種關系，所以，只需求解其中一個較小規模的子問只需求解其中一個較小規模的子問題就可以得到

4、原問題的解題就可以得到原問題的解。 子問題子問題 的規模是的規模是n/2 子問題的解子問題的解 原問題的解原問題的解 原問題原問題 的規模是的規模是n 子問題子問題 的規模是的規模是n/2減治法的設計思想減治法的設計思想 例：計算例：計算an的值，的值，應用應用減治技術減治技術得到如下計算方法：得到如下計算方法：應用應用分治法分治法得到得到an的計算方法是：的計算方法是： 1122naanaannnO (log2n)O (n log2n) - -且是奇數且是奇數且是偶數且是偶數1)(1)(122) 1(22naananaannn減治法的設計思想減治法的設計思想 111)2/(0)(nnnTnT

5、 所以，通常來說，所以，通常來說，應用減治法應用減治法處理問題的效率是很高的，處理問題的效率是很高的，一般是一般是O( (log2n) )數量級數量級。 減治法只對一個子問題求解減治法只對一個子問題求解，并且，并且不需要解的合并不需要解的合并。應。應用減治法（例如減半法）得到的算法通常具有如下遞推式：用減治法（例如減半法）得到的算法通常具有如下遞推式： 減治法的設計思想減治法的設計思想 對比分治法：對比分治法： 足夠小nnfnTngnT)()2/(2)()(減治法的設計思想減治法的設計思想 一個簡單的例子一個簡單的例子兩個序列的中位數兩個序列的中位數問題描述：一個長度為問題描述：一個長度為n（

6、n1）的升序序）的升序序列列S，處在第，處在第n/2個位置的數稱為序列個位置的數稱為序列S的中的中位數位數 。兩個序列的中位數是他們。兩個序列的中位數是他們所有所有元素的元素的升序序列的中位數。現有兩個等長升序序列升序序列的中位數。現有兩個等長升序序列A和和B，試設計一個在時間和空間兩方面都，試設計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列的中位數。盡可能高效的算法，找出兩個序列的中位數。A=11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，則中位數為，則中位數為13減治法的設計思想減治法的設計思想 想法想法 分別求出兩個序列的中位數，記為分別求出兩個序

7、列的中位數，記為a和和b；比較比較a和和b，有下列三種情況：，有下列三種情況： a = b：則：則a即為兩個序列的中位數；即為兩個序列的中位數； a b：則中位數只能出現在：則中位數只能出現在b和和a之間，在序列之間，在序列A中舍棄中舍棄a之后的元素得到序列之后的元素得到序列A1，在序列，在序列B中舍棄中舍棄b之前的元素得到序列之前的元素得到序列B1；在在A1和和B1中分別求出中位數，重復上述過程，直中分別求出中位數，重復上述過程，直到兩個序列中只有一個元素，則較小者即為所求。到兩個序列中只有一個元素，則較小者即為所求。減治法的設計思想減治法的設計思想 對于兩個給定的序列對于兩個給定的序列A=

8、11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，求序列，求序列A和和B的中位數的過程。的中位數的過程。步驟步驟操作說明操作說明序列序列A序列序列B1初始序列初始序列11, 13, 15, 17, 192, 4, 10, 15, 202分別求中位數分別求中位數11, 13, 15, 17, 192, 4, 10, 15, 2031510，結果在，結果在10, 15之間之間舍棄舍棄15之后元素，之后元素，11,13,15舍棄舍棄10之前元素，之前元素，10,15,204分別求中位數分別求中位數11,13,1510,15,2051315，結果在，結果在11, 15之間之

9、間舍棄舍棄13之前元素，之前元素，13,15舍棄舍棄15之后元素，之后元素，10,156分別求中位數分別求中位數13,1510,1571013，結果在，結果在10, 13之間之間舍棄舍棄13之后元素，之后元素，13舍棄舍棄10之前元素，之前元素，158長度為長度為1，較小者為所求，較小者為所求1315減治法的設計思想減治法的設計思想 算法算法5.1：兩個序列中位數：兩個序列中位數SearchMid輸入：兩個長度為輸入：兩個長度為n的有序序列的有序序列A和和B輸出：序列輸出：序列A和和B的中位數的中位數1. 循環直到序列循環直到序列A和序列和序列B均只有一個元素均只有一個元素 1.1 a = 序

10、列序列A的中位數；的中位數； 1.2 b = 序列序列B的中位數；的中位數； 1.3 比較比較a和和b，執行下面三種情況之一：，執行下面三種情況之一： 1.3.1 若若a=b，則返回，則返回a，算法結束；，算法結束； 1.3.2 若若ab，則在序列，則在序列A中舍棄中舍棄a之后的元素，在序列之后的元素，在序列B中中舍棄舍棄b之前的元素，轉步驟之前的元素，轉步驟1； 2. 序列序列A和序列和序列B均只有一個元素，返回較小者；均只有一個元素，返回較小者；減治法的設計思想減治法的設計思想 算法分析算法分析 由于每次求兩個序列的中位數后，得到由于每次求兩個序列的中位數后，得到的兩個子序列的長度都是上一

11、個序列的一半，故循的兩個子序列的長度都是上一個序列的一半，故循環共執行環共執行log2n次，時間復雜性為次，時間復雜性為O( log2n)。算法除簡單變量外沒有額外開辟臨時空間，故空間算法除簡單變量外沒有額外開辟臨時空間，故空間復雜性為復雜性為O(1)。第第5章章 減治法減治法 5.1 概述概述 5.2 查找問題中的減治法查找問題中的減治法5.3 排序問題中的減治法排序問題中的減治法5.4 組合問題中的減治法組合問題中的減治法閱讀材料閱讀材料 假幣問題的復雜版本假幣問題的復雜版本5.2 查找問題中的減治法查找問題中的減治法 5.2.1 折半查找折半查找 5.2.2 二叉查找樹二叉查找樹基本思想

12、：基本思想：(1)(1)取中間記錄作為比較對象取中間記錄作為比較對象，若給定值與中間記錄的關鍵碼，若給定值與中間記錄的關鍵碼相等，則查找成功；相等，則查找成功；(2)(2)若給定值小于中間記錄的關鍵碼，則若給定值小于中間記錄的關鍵碼，則在中間記錄的在中間記錄的左半區左半區繼續查找；繼續查找；(3)(3)若給定值大于中間記錄的若給定值大于中間記錄的關鍵碼，則在中間記錄的關鍵碼，則在中間記錄的右半區右半區繼續查找。繼續查找。重復上述過程，直到成功，或所查找的區域無記錄，查找失重復上述過程，直到成功，或所查找的區域無記錄，查找失敗。敗。 折半查找折半查找 r1 rmid- -1 rmid rmid+

13、1 rn （mid=( (1+n) )/2）如果如果 krmid 查找這里查找這里特點：每次與中間記錄比較特點：每次與中間記錄比較 k 問題問題 ：在有序表中查找值為在有序表中查找值為k k的記錄的記錄例：查找值為例：查找值為14的記錄的過程的記錄的過程0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52low=1high=13mid=7 high=6 mid=3 high=2 mid=1 31141814714low=2mid=2 14=14算法算法5.1折半查找折半查找輸入：有序序列輸入：有序序列r1,

14、r2,rn，待查值，待查值k輸出：若成功返回記錄輸出：若成功返回記錄k的位置，否則返回失敗標志的位置，否則返回失敗標志0 1. low=1；high=n； /設置初始查找區間設置初始查找區間 2. 測試查找區間測試查找區間low，high是否存在，若不存在，則查找失敗；是否存在，若不存在，則查找失敗； 否則否則 3. 取中間點取中間點mid=( (low+high) )/2; 比較比較k與與rmid，有以下三種情況：，有以下三種情況： 3.1 若若krmid，則，則 low=mid+1；查找在右半區進行，轉；查找在右半區進行，轉2； 3.3 若若k=rmid，則查找成功，返回記錄在表中位置，則

15、查找成功，返回記錄在表中位置mid；折半查找折半查找 算法分析算法分析 用判定樹描述折半查找的判定過程。每個結用判定樹描述折半查找的判定過程。每個結點對應有序序列中的一個記錄，結點值為該記錄在有序點對應有序序列中的一個記錄，結點值為該記錄在有序序列中的位置。長度為序列中的位置。長度為n的判定樹的構造方法為：的判定樹的構造方法為： （1）當）當n=0時，判定樹為空；時，判定樹為空；（2）當）當n0時，時， 根結點：根結點：是有序表中序號為是有序表中序號為mid=(n+1)/2的記錄；的記錄； 左子樹：左子樹：是有序表是有序表r1 rmid-1對應的判定樹；對應的判定樹； 右子樹：右子樹：是與是與

16、rmid+1 rn相對應的判定樹相對應的判定樹折半查找折半查找 6312548111079 查找查找k k過程：過程：從根結點從根結點該記錄結點的路徑；該記錄結點的路徑； 和和K K值的比較次數：值的比較次數：等于該記錄結點在樹中的等于該記錄結點在樹中的層數層數。具有。具有n個結點的判定數的深度為個結點的判定數的深度為 。1log2n折半查找折半查找 5.2 查找問題中的減治法查找問題中的減治法 5.2.1 折半查找折半查找 5.2.2 二叉查找樹二叉查找樹二叉查找樹二叉查找樹BST 二叉查找樹二叉查找樹BST 由由二叉排序樹的定義二叉排序樹的定義，在二叉排序樹，在二叉排序樹root中查找給定

17、值中查找給定值k的的過程是：過程是： 若若root是空樹，則查找失敗；是空樹，則查找失敗； 若若k根結點的值，則查找成功；根結點的值，則查找成功； 否則，若否則，若k根結點的值根結點的值，則在，則在root左子樹上查找左子樹上查找； 否則，在否則，在root的的右子樹上查找右子樹上查找； 上述過程一直持續到上述過程一直持續到k被找到被找到或者或者待查找的子樹為空待查找的子樹為空，如，如果待查找的子樹為空，果待查找的子樹為空，則查找失敗則查找失敗。v二叉排序樹的二叉排序樹的查找效率查找效率就在于只需要就在于只需要查找兩個子樹之一查找兩個子樹之一。 58427090634555836710二叉查找

18、樹二叉查找樹BST 查找查找58與與95記錄的示例記錄的示例二叉排序樹的結點結構為：二叉排序樹的結點結構為：struct BiNode int data; /結點的值，假設查找集合的元素為整型結點的值，假設查找集合的元素為整型 BiNode *lchild, *rchild; /指指向左向左、右子樹右子樹的指針的指針 ;算法算法5.2二叉排序樹的查找二叉排序樹的查找 BiNode * SearchBST(BiNode * root, int k) if (root= =NULL) return NULL； else if (root-data=k) return root; else if (

19、kdata) return SearchBST(root-lchild, k); else return SearchBST(root-rchild, k); C+描述二叉查找樹二叉查找樹BSTBST 建立二叉查找樹算法建立二叉查找樹算法BiNode* InsertBST(BiNode* root, int data) if(root=NULL) root=new BiNode; root-data=data;/申請一個新結點申請一個新結點 root-lchild=root-rchild=NULL;/葉子結點葉子結點 return root; if(datadata)root-lchild=I

20、nsertBST(root-lchild, data); elseroot-rchild=InsertBST(root-rchild, data);return root;二叉查找樹二叉查找樹BSTBST BiNode* createBST(int a, int n) /建立二叉查找樹建立二叉查找樹 BiNode* T=NULL; for(int i=0; in; i+)T=InsertBST(T, ai); /在二叉查找樹在二叉查找樹 T中插入中插入ai return T;二叉查找樹二叉查找樹BSTBST 二叉查找樹二叉查找樹BSTBST 按按63,90,55,58,70,42,10,45,

21、83,67順序構造的二叉排序樹順序構造的二叉排序樹58427090634555836710二叉查找樹二叉查找樹BSTBST 1log2n問題問題 設無序序列設無序序列 T =(r1, r2, , rn)，T 的第的第k（1kn）小元素定義為小元素定義為T 按升序排列后在第按升序排列后在第k個位置上的元素。給定一個位置上的元素。給定一個序列個序列T和一個整數和一個整數k，尋找，尋找 T 的第的第k小元素的問題稱為小元素的問題稱為選擇問選擇問題題。特別地，將尋找第。特別地，將尋找第n/2小元素的問題稱為小元素的問題稱為中值問題中值問題。 5.2.3 5.2.3 選擇問題選擇問題想法想法 固然可將固

22、然可將T排序后取第排序后取第k個元素，但排序算法最好時間個元素，但排序算法最好時間是是O(nlog2n)，如應用減治技術，可將算法平均時間性能提高，如應用減治技術，可將算法平均時間性能提高到到O(n)。考慮。考慮快速排序快速排序中的劃分過程，一般情況下，設待劃中的劃分過程，一般情況下，設待劃分的序列為分的序列為ri rj，選定一個軸值將序列，選定一個軸值將序列ri rj進行劃分，使進行劃分，使得比軸值小的元素都位于軸值的左側，比軸值大的元素都位得比軸值小的元素都位于軸值的左側，比軸值大的元素都位于軸值的右側，假定軸值的最終位置是于軸值的右側，假定軸值的最終位置是s，則：，則：（1）若）若k=s

23、，則，則rs就是第就是第k小元素；小元素；（2）若）若ks，則第，則第k小元素一定在序列小元素一定在序列rs+1 rj中；中；無論上面哪種情況，或者已經得到結果，或者將選擇問無論上面哪種情況，或者已經得到結果，或者將選擇問題的查找區間減少一半（如果軸值恰好是序列的中值）題的查找區間減少一半（如果軸值恰好是序列的中值）5.2.3 5.2.3 選擇問題選擇問題 ri rk rs- -1 rs rs+1 rj 均均rs 軸值軸值 均均rs ri rs- -1 rs rs+1 rk rj 均均rs 軸值軸值 均均rs(a) 若若ks，則，則rk在右半區在右半區選擇問題的例子選擇問題的例子: :查找第查

24、找第4小元素小元素5 3 8 1 4 6 9 2 7以以5為軸值劃分序列為軸值劃分序列42，只在右側查找，只在右側查找以以4為軸值劃分序列為軸值劃分序列44，軸值即為第，軸值即為第4小元素小元素 2 3 4 1 5 6 9 8 7 2 3 4 1 1 2 4 3 4 3 3 4 5.2.3 5.2.3 選擇問題選擇問題算法算法選擇問題選擇問題輸入：無序序列輸入：無序序列r ，位置，位置k輸出：返回第輸出：返回第k小的元素值小的元素值 1. i=1; j=n; /設置初始查找區間設置初始查找區間 2. 以以ri為軸值對序列為軸值對序列rirj進行一次劃分，得到軸進行一次劃分，得到軸值的位置值的位

25、置s; 3. 將軸值位置將軸值位置s與與k比較比較 3.1 如果如果k=s，則將，則將rs作為結果返回；作為結果返回； 3.2 否則，如果否則，如果ks，則，則j=s-1，轉步驟，轉步驟2； 3.3 否則，否則，i=s+1，轉步驟，轉步驟2；5.2.3 5.2.3 選擇問題選擇問題最好情況最好情況：每次劃分的軸值恰好是序列的中值，則可以保證處每次劃分的軸值恰好是序列的中值，則可以保證處理的區間比上一次減半，由于在一次劃分后，只需處理一個子理的區間比上一次減半，由于在一次劃分后，只需處理一個子序列，所以，比較次數的遞推式是：序列，所以，比較次數的遞推式是： ( )(2)( )( )T nT nO

26、 nO n最壞情況最壞情況：每次劃分的軸值恰好是序列中的最大值或最小值，每次劃分的軸值恰好是序列中的最大值或最小值，則處理區間只能比上一次減少則處理區間只能比上一次減少1個，所以，比較次數的遞推式是：個，所以，比較次數的遞推式是：平均情況平均情況：假設每次劃分的軸值是劃分序列中的一個隨機位置：假設每次劃分的軸值是劃分序列中的一個隨機位置的元素，則處理區間按照一種隨機的方式減少，可以證明，算的元素，則處理區間按照一種隨機的方式減少，可以證明，算法的平均時間是法的平均時間是O(n) 。 )2()()1()(nOnOnTnT - - 5.2.3 5.2.3 選擇問題選擇問題第第5章章 減治法減治法

27、5.1 概述概述 5.2 查找問題中的減治法查找問題中的減治法5.3 排序問題中的減治法排序問題中的減治法5.4 組合問題中的減治法組合問題中的減治法閱讀材料閱讀材料 假幣問題的復雜版本假幣問題的復雜版本5.3 排序問題中的減治法排序問題中的減治法 5.3.1 插入排序插入排序5.3.2 堆排序堆排序每次將無序區第每次將無序區第1條記錄插入到有序區適當位置。初條記錄插入到有序區適當位置。初始取第始取第1條記錄為有序區，其它記錄為無序區。隨著條記錄為有序區，其它記錄為無序區。隨著排序進行，有序區不斷擴大，無序區不斷縮小。最終排序進行，有序區不斷擴大，無序區不斷縮小。最終無序區為空，有序區包含了全

28、部記錄，排序結束。無序區為空，有序區包含了全部記錄，排序結束。 有序區也可從排序表的尾部生成有序區也可從排序表的尾部生成 。在插入第在插入第 i（i1）個記錄時，前面的）個記錄時，前面的 i-1個記錄已經排好序個記錄已經排好序。 有序序列有序序列無序序列無序序列r1r2ri-1rirnri+1r1r2ri-1rirnri+1（1）如何構造初始的有序序列？）如何構造初始的有序序列？( (待排序序列第一個記錄）待排序序列第一個記錄）（2）如何查找待插入記錄的插入位置）如何查找待插入記錄的插入位置?需解決的關鍵問題需解決的關鍵問題? 初始：（初始：（49）38 13 76 27 49 （38 49）

29、13 76 27 49 （13 38 49）76 27 49 （13 38 49 76）27 49 （13 27 38 49 76 ）49 （13 27 38 49 49 76 ）自右向左順自右向左順序查找插入序查找插入的位置的位置r 0 1 2 3 4 5 6211825221025*212125插入排序插入排序i = 218221025*25i = 318221025*2225222110252115102525*2521151025*252118151018181025*i = 418i = 61825*i = 5r0的作用的作用?暫存單元暫存單元監視哨監視哨25void InsertS

30、ort(int r,int n) /設置監視哨設置監視哨for(int i=2;i=n;i+)/進行進行n-1次插入，依次插入次插入，依次插入 /r2,r3,rn r0=ri; /r0是監視哨是監視哨 /順序比較和移動，查找順序比較和移動，查找ri的插入位置的插入位置 for(int j=i-1;r0rj;j-) rj+1=rj; /記錄后移，繼續向前搜索記錄后移，繼續向前搜索 rj+1=r0; /插入插入ri r0為為監視哨監視哨（Sentinel），省略下標越界檢查），省略下標越界檢查“j1”：一旦越界，：一旦越界，j=01，循環，循環條件條件r0 n/2 的結點都是葉子，以這些結點為根的

31、的結點都是葉子，以這些結點為根的子樹均已是堆。（即葉子已是堆）子樹均已是堆。（即葉子已是堆）q依次將以序號為依次將以序號為 n/2 ， n/2 1,1的結點作的結點作為根的子樹都調整為堆。為根的子樹都調整為堆。q按該次序調整各結點時，其左、右子樹均已是堆。按該次序調整各結點時，其左、右子樹均已是堆。堆排序堆排序 1 19 98 810106 616162 211114 45 5n=10，故從第，故從第 10/2 5個結點開始進行調整個結點開始進行調整 1 19 98 810106 616162 211115 54 41 19 98 810106 611112 216165 54 41 19 9

32、8 810106 611112 216165 54 41 19 98 810106 6111116162 25 54 41 19 98 810106 62 2161611115 54 416169 98 810106 62 21 111115 54 416169 98 810106 62 211111 15 54 416169 98 81 16 62 2111110105 54 4堆排序堆排序 堆調整堆調整篩選法篩選法 關鍵問題：完全二叉樹中，根結點的左右子關鍵問題：完全二叉樹中，根結點的左右子樹均是堆，如何調整根結點，使整個完全二叉樹樹均是堆，如何調整根結點，使整個完全二叉樹成為一個堆？成為

33、一個堆？ (a) 28與與35交換交換(b) 28與與32交換交換(c) 將將28篩到葉子篩到葉子283218201218201235321820123535283228堆排序堆排序 qRi左、右子樹是堆，子樹的根為各自子樹中關鍵字最大者，左、右子樹是堆，子樹的根為各自子樹中關鍵字最大者，q將將Ri和其左、右孩子中關鍵字最大者進行比較。和其左、右孩子中關鍵字最大者進行比較。若若Ri最大，則無需調整，以其為根的子樹已是堆；最大，則無需調整，以其為根的子樹已是堆；否則，將否則，將Ri和具有最大關鍵字的左孩子和具有最大關鍵字的左孩子R2i或右孩子或右孩子R2i+1進行交換。進行交換。q交換后以交換后

34、以R2i和和R2i+1為根的子樹可能不再是堆，但其左、為根的子樹可能不再是堆，但其左、右子樹仍然是堆，于是重復上述過程，右子樹仍然是堆，于是重復上述過程，將子樹調整為堆將子樹調整為堆，如此逐層遞推下去，最多可能一直調整到樹葉。如此逐層遞推下去，最多可能一直調整到樹葉。q這一過程就像過篩子一樣，把較小的關鍵字篩下去，而將最大這一過程就像過篩子一樣，把較小的關鍵字篩下去，而將最大關鍵字一層層地選擇上來。關鍵字一層層地選擇上來。 堆調整堆調整篩選法篩選法19 98 810106 62 21611115 54 4大根堆大根堆16169 98 810106 62 21 111115 54 416169

35、98 810106 62 211111 15 54 416169 98 81 16 62 2111110105 54 4 設要篩選結點的編號為設要篩選結點的編號為k，堆中最后一個結點的編號為，堆中最后一個結點的編號為n，并，并且結點且結點k的左右子樹均是堆（即的左右子樹均是堆（即rk+1 rn滿足堆的條件滿足堆的條件) ) 算法算法5.3篩選法調整堆篩選法調整堆 1. 設置設置i和和j，分別指向當前要篩選的結點和要篩選結點的左孩子；，分別指向當前要篩選的結點和要篩選結點的左孩子； 2. 若結點若結點i已是葉子，則篩選完畢；否則，比較要篩選結點的左右已是葉子，則篩選完畢；否則，比較要篩選結點的左

36、右 孩子結點，并將孩子結點，并將j指向關鍵碼較大的結點；指向關鍵碼較大的結點； 3. 將要篩選結點將要篩選結點i的關鍵碼與結點的關鍵碼與結點j的關鍵碼進行比較，有以下兩種的關鍵碼進行比較，有以下兩種情況：情況： 3.1 如果結點如果結點i的關鍵碼大，則完全二叉樹已經是堆；的關鍵碼大，則完全二叉樹已經是堆； 3.2 否則將否則將ri與與rj交換；令交換；令i=j，轉步驟，轉步驟2繼續進行篩選；繼續進行篩選；時間性能是時間性能是O(log2n)。 堆調整堆調整篩選法篩選法算法算法5.4篩選法調整堆篩選法調整堆 void SiftHeap( (int r , int k, int n) ) i=k;

37、 j=2*i; /置置i為要篩的結點，為要篩的結點，j為為i的左孩子的左孩子 while ( (j=n) ) /篩選還沒有進行到葉子篩選還沒有進行到葉子 if ( (jn & rjrj) ) /根結點已經大于左右孩子中的較大者根結點已經大于左右孩子中的較大者 break; else rirj; /將根結點與結點將根結點與結點j交換交換 i=j; j=2*i; /被篩結點位于原來結點被篩結點位于原來結點j的位置的位置 C+描述堆調整堆調整篩選法篩選法16169 98 81 16 62 2111110105 54 4交換交換篩選篩選交換交換篩選篩選4 49 98 81 16 62 2111

38、110105 5161611119 98 81 16 62 210104 45 516162 29 98 81 16 6111110104 45 51616經過跟剛才一樣的步驟經過跟剛才一樣的步驟堆排序堆排序交換交換篩選篩選交換交換篩選篩選10109 98 81 16 611115 54 42 216161 19 98 810106 611115 54 42 216169 98 81 110106 611115 54 42 216161 18 89 910106 611115 54 42 21616交換交換篩選篩選交換交換篩選篩選8 86 69 910101 111115 54 42 2161

39、61 16 69 910108 811115 54 42 216166 61 19 910108 811115 54 42 216162 21 19 910108 811115 54 46 61616交換交換篩選篩選交換交換篩選篩選5 51 19 910108 811114 42 26 616162 21 19 910108 811114 45 56 616164 41 19 910108 811112 25 56 616161 14 49 910108 811112 25 56 61616交換交換2 24 49 910108 811111 15 56 616161 14 49 910108

40、811112 25 56 61616第第5章章 減治法減治法 5.1 概述概述 5.2 查找問題中的減治法查找問題中的減治法5.3 排序問題中的減治法排序問題中的減治法5.4 組合問題中的減治法組合問題中的減治法閱讀材料閱讀材料 假幣問題的復雜版本假幣問題的復雜版本5.4 組合問題中的減治法組合問題中的減治法 5.4.1 淘汰賽冠軍問題淘汰賽冠軍問題 5.4.2 假幣問題假幣問題淘汰賽冠軍問題淘汰賽冠軍問題問題問題 假設有假設有n=2k個選手進行個選手進行競技淘汰賽競技淘汰賽，最后決出冠，最后決出冠軍的選手，請設計淘汰賽的過程。軍的選手，請設計淘汰賽的過程。想法想法 分治法是將所有選手分成兩部

41、分，每部分決出分治法是將所有選手分成兩部分，每部分決出勝者后，讓這些勝者再進行比賽，最后決出冠軍。勝者后，讓這些勝者再進行比賽，最后決出冠軍。減治法：將所有選手分成減治法：將所有選手分成n/2組，每組兩個選手比賽，組，每組兩個選手比賽，敗者被淘汰，然后再將剩余選手分成敗者被淘汰，然后再將剩余選手分成n/4組，每組兩個組，每組兩個選手進行比賽，選手進行比賽，直到剩余最后兩個選手決出冠軍。直到剩余最后兩個選手決出冠軍。12( )2 ( /2) 12nT nT nnT（n）=O(n)算法算法5.8淘汰賽冠軍問題淘汰賽冠軍問題 string Game(string r , int n) i=n; wh

42、ile (i1) i=i/2; for (j=0; ji; j+) if (Comp(rj+i, rj) rj=rj+i; /勝者放在勝者放在 rj 中中, j=0,1,2,i/2 -1 return r0; C+描述淘汰賽冠軍問題淘汰賽冠軍問題算法分析算法分析 因為因為n=2k，所以，外層的，所以，外層的while循環共循環共執行執行k次，在每一次執行時，內層的次，在每一次執行時，內層的for循環的執行循環的執行次數分別是次數分別是n/2，n/4，1，而函數，而函數comp可以在可以在常數時間內完成，因此，算法常數時間內完成，因此，算法5.8的執行時間為：的執行時間為：)(1)211 (2)

43、(1nOnnnnTkkii-淘汰賽冠軍問題淘汰賽冠軍問題5.4 組合問題中的減治法組合問題中的減治法 5.4.1 淘汰賽冠軍問題淘汰賽冠軍問題 5.4.2 假幣問題假幣問題假幣問題假幣問題? ? 問題問題 在在n枚枚外觀相同的硬幣中，外觀相同的硬幣中，有一枚是假幣有一枚是假幣，并且并且已知假幣較輕已知假幣較輕。可以通過一架天平來任意比。可以通過一架天平來任意比較兩組硬幣，從而得知兩組硬幣的重量是否相同，較兩組硬幣，從而得知兩組硬幣的重量是否相同，或者哪一組更輕一些，但不知道輕多少，或者哪一組更輕一些，但不知道輕多少，假幣問假幣問題是要求設計一個高效的算法來檢測出這枚假幣題是要求設計一個高效的算法來檢測出這枚假幣。 2n假幣問題假幣問題 在假幣問題中，在假幣問題中，每次用天平比較后每次用天平比較后，只需解決一只需解決一個規模減半的問題個規模減半的問題，所以，所以，它屬于