第5章_减治法

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假币问题假币问题 在假币问题中，在假币问题中，每次用天平比较后每次用天平比较后，只需解决一只需解决一个规模减半的问题个规模减半的问题，所以，所以，它属于