堆和不相交数据结构精选PPT.ppt

《堆和不相交数据结构精选PPT.ppt》由会员分享，可在线阅读，更多相关《堆和不相交数据结构精选PPT.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、堆和不相交数据结构第1页，讲稿共49张，创作于星期日二叉树性质二叉树性质二叉树性质二叉树性质 (Page 71)(Page 71)性质性质性质性质1 1：在二叉树中，第：在二叉树中，第：在二叉树中，第：在二叉树中，第j j层的顶点数最多是层的顶点数最多是层的顶点数最多是层的顶点数最多是2 2j j。性质性质性质性质2 2：令二叉树：令二叉树：令二叉树：令二叉树T T顶点数是顶点数是顶点数是顶点数是n n，高度是，高度是，高度是，高度是k k，那么，那么，那么，那么如果如果如果如果T T是完全的，等号成立。如果是完全的，等号成立。如果是完全的，等号成立。如果是完全的，等号成立。如果T T是几乎完

2、全的，那么是几乎完全的，那么是几乎完全的，那么是几乎完全的，那么性质性质性质性质3 3：有：有：有：有n n个顶点的完全或几乎完全的二叉树的高度是个顶点的完全或几乎完全的二叉树的高度是个顶点的完全或几乎完全的二叉树的高度是个顶点的完全或几乎完全的二叉树的高度是性质性质4 4：对任何一棵二叉树：对任何一棵二叉树T T，如果其终端结点数为如果其终端结点数为n0n0，度为度为2 2的结点数为的结点数为n2n2，则则n0=n2+1n0=n2+12第2页，讲稿共49张，创作于星期日性质：对任何一棵二叉树性质：对任何一棵二叉树T T，如果其终端结点数为如果其终端结点数为n0n0，度为度为2 2的的结点数为

3、结点数为n2n2，则则n0=n2+1n0=n2+1证明：证明：n1为二叉树为二叉树T中度为中度为1的结点数的结点数 因为：二叉树中所有结点的度均小于或等于因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一个又二叉树中，除根结点外，其余结点都只有一个 分支进入分支进入 设设B为分支总数，则为分支总数，则n=B+1 又：分支由度为又：分支由度为1和度为和度为2的结点射出，的结点射出，B=n1+2n2 于是，于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1第3页，讲稿共49张，创作于星期日性质性

4、质性质性质5 5：如果对一棵有：如果对一棵有：如果对一棵有：如果对一棵有n n个结点的完全二叉树的结点按层序个结点的完全二叉树的结点按层序个结点的完全二叉树的结点按层序个结点的完全二叉树的结点按层序编号，则对任一结点编号，则对任一结点编号，则对任一结点编号，则对任一结点i(1 i n)，有：，有：，有：，有：(1)(1)如果如果如果如果i=1i=1，则结点，则结点，则结点，则结点i i是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果i1i1，则，则，则，则其双亲是其双亲是其双亲是其双亲是 i/2 (2)(2)如果如果如果如果2in2in，

5、则结点，则结点，则结点，则结点i i无左孩子；如果无左孩子；如果无左孩子；如果无左孩子；如果2i n，则其左孩子，则其左孩子，则其左孩子，则其左孩子是是是是2i2i (3)(3)如果如果如果如果2i+1n2i+1n，则结点，则结点，则结点，则结点i i无右孩子；如果无右孩子；如果无右孩子；如果无右孩子；如果2i+1 n，则其右，则其右，则其右，则其右孩子是孩子是孩子是孩子是2i+12i+14第4页，讲稿共49张，创作于星期日4.1 引言（堆、不相交集）引言（堆、不相交集）4.2 堆堆 4.2.1 堆上的运算堆上的运算 4.2.2 创建堆创建堆 4.2.3 堆排序堆排序 4.2.4 最大堆和最小

6、堆最大堆和最小堆4.3 不相交集数据结构不相交集数据结构 4.3.1 按秩合并措施按秩合并措施 4.3.3 Union-Find算法算法 4.3.2 路径压缩路径压缩 4.3.4 Union-Find算法的分析（略）算法的分析（略）5第5页，讲稿共49张，创作于星期日4.2 堆堆堆的引入堆的引入在许多算法中，需要支持下面二种运算：在许多算法中，需要支持下面二种运算：在许多算法中，需要支持下面二种运算：在许多算法中，需要支持下面二种运算：u插入元素插入元素u寻找最大值元素（或最小值元素）寻找最大值元素（或最小值元素）支持这二种运算的数据结构称为优先队列。支持这二种运算的数据结构称为优先队列。支持

7、这二种运算的数据结构称为优先队列。支持这二种运算的数据结构称为优先队列。可采用下述三种方法实现优先队列：可采用下述三种方法实现优先队列：可采用下述三种方法实现优先队列：可采用下述三种方法实现优先队列：使用普通队列（或数组），插入容易（尾部），但使用普通队列（或数组），插入容易（尾部），但使用普通队列（或数组），插入容易（尾部），但使用普通队列（或数组），插入容易（尾部），但寻找最大值需搜索整个队列，开销比较大。寻找最大值需搜索整个队列，开销比较大。寻找最大值需搜索整个队列，开销比较大。寻找最大值需搜索整个队列，开销比较大。使用排序数组，寻找最大值元素容易，插入操作需使用排序数组，寻找最大值元素

8、容易，插入操作需使用排序数组，寻找最大值元素容易，插入操作需使用排序数组，寻找最大值元素容易，插入操作需移动很多元素。移动很多元素。移动很多元素。移动很多元素。使用堆，寻找最大值元素容易，插入操作仅需移动使用堆，寻找最大值元素容易，插入操作仅需移动使用堆，寻找最大值元素容易，插入操作仅需移动使用堆，寻找最大值元素容易，插入操作仅需移动少量元素。少量元素。少量元素。少量元素。6第6页，讲稿共49张，创作于星期日定义定义4.1（Page 74）一个（二叉）堆是一棵几乎完全的二叉树，它的每个一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设结点都满足堆的特性：设v是一个结点，是一个

9、结点，p(v)是是v的父的父结点，那么存储在结点，那么存储在p(v)中的数据项键值大于或等于存中的数据项键值大于或等于存储在储在v中的数据项键值。中的数据项键值。堆的定义（二叉堆）堆的定义（二叉堆）几乎完全二叉树（几乎完全二叉树（几乎完全二叉树（几乎完全二叉树（Page 71Page 71）如果一棵二叉树，除了如果一棵二叉树，除了如果一棵二叉树，除了如果一棵二叉树，除了最右边最右边最右边最右边位位位位置上的一个或几个置上的一个或几个置上的一个或几个置上的一个或几个叶子叶子叶子叶子可能缺少外，可能缺少外，可能缺少外，可能缺少外，它是丰满的，我们定义它为几乎完全它是丰满的，我们定义它为几乎完全它是

10、丰满的，我们定义它为几乎完全它是丰满的，我们定义它为几乎完全二叉树。二叉树。二叉树。二叉树。几乎完全二叉树例几乎完全二叉树例几乎完全二叉树例几乎完全二叉树例7第7页，讲稿共49张，创作于星期日堆数据结构支持下列运算堆数据结构支持下列运算uDeleteMax(H)：从一个非空堆：从一个非空堆H中，删除最大中，删除最大键值的数据项，并返回该数据；键值的数据项，并返回该数据；uInsert(H,x)：将数据项：将数据项x插入堆插入堆H中；中；uDelete(H,i)：从堆中删除第：从堆中删除第i项；项；uMakeHeap(A)：将数组转换为堆。：将数组转换为堆。堆的蕴含特性：堆的蕴含特性：沿着每条从

11、根到叶子的路径，元素的键值以降序沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。（或称非升序）排列。8第8页，讲稿共49张，创作于星期日堆的表示堆的表示 有有有有n n个结点堆个结点堆个结点堆个结点堆T T，可以用一个数组，可以用一个数组，可以用一个数组，可以用一个数组H1.nH1.n用下面方式来表示：用下面方式来表示：用下面方式来表示：用下面方式来表示：uuT T的根结点存储在的根结点存储在的根结点存储在的根结点存储在H1H1中；中；中；中；uu设设设设T T的结点存储在的结点存储在的结点存储在的结点存储在HHj j 中，如果它有左子结点，则这个中，如果它有左子结点，则这个中，

12、如果它有左子结点，则这个中，如果它有左子结点，则这个左子结点存储在左子结点存储在左子结点存储在左子结点存储在H2H2j j 中。如果它还有右子结点，这个右子中。如果它还有右子结点，这个右子中。如果它还有右子结点，这个右子中。如果它还有右子结点，这个右子结点存储在结点存储在结点存储在结点存储在H2H2j j+1+1；uu若元素若元素若元素若元素HHj j 不是根结点，它的父结点存储在不是根结点，它的父结点存储在不是根结点，它的父结点存储在不是根结点，它的父结点存储在HH j j/2/2 中。中。中。中。由由由由“几乎完全二叉树几乎完全二叉树几乎完全二叉树几乎完全二叉树”的定义可知，如果堆中某结点

13、有右子的定义可知，如果堆中某结点有右子的定义可知，如果堆中某结点有右子的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。结点，则它一定也有左子结点。结点，则它一定也有左子结点。结点，则它一定也有左子结点。堆具有如下性质：堆具有如下性质：堆具有如下性质：堆具有如下性质：key(Hkey(H j j/2/2 )key(H)key(Hj j)2 2 j jnn9第9页，讲稿共49张，创作于星期日2011729310411546573879510堆和它的数组表示法堆和它的数组表示法堆和它的数组表示法堆和它的数组表示法 把存储在堆中的数据项视为键值。按树的结点把存储在堆中的数据项视为键值。按树

14、的结点把存储在堆中的数据项视为键值。按树的结点把存储在堆中的数据项视为键值。按树的结点“自顶向下自顶向下自顶向下自顶向下”、“从左至右从左至右从左至右从左至右”、“按按按按1 1到到到到n n”的顺序进行编号，那么数组元的顺序进行编号，那么数组元的顺序进行编号，那么数组元的顺序进行编号，那么数组元素素素素HiHi对应树中编号为对应树中编号为对应树中编号为对应树中编号为i i的结点。的结点。的结点。的结点。2 20 01 17 79 91 10 01 11 14 45 53 37 75 51 12 23 34 45 56 67 78 89 91010H2=17H2=17的的的的左子结点左子结点左

15、子结点左子结点为为为为HH2*22*2=H4=10=H4=10H2H2=17=17的的的的右子结点右子结点右子结点右子结点为为为为HH2*2+12*2+1=H5=11=H5=11H9=7H9=7的的的的父结点父结点父结点父结点为为为为H H 9/29/2 =H4=10=H4=10 沿着每条从根到叶子沿着每条从根到叶子的路径，元素的键值以的路径，元素的键值以降序排列。降序排列。10第10页，讲稿共49张，创作于星期日4.2.1 堆上的运算堆上的运算ShiftUp 假定对于某个假定对于某个假定对于某个假定对于某个i i1 1，HHi i 的键值变成大于它父结点的键值，的键值变成大于它父结点的键值，

16、的键值变成大于它父结点的键值，的键值变成大于它父结点的键值，这样违反了堆的特性，需使用称为这样违反了堆的特性，需使用称为这样违反了堆的特性，需使用称为这样违反了堆的特性，需使用称为ShiftUpShiftUp的运算来修复堆。的运算来修复堆。的运算来修复堆。的运算来修复堆。ShiftUpShiftUp运算沿着从运算沿着从运算沿着从运算沿着从HHi i 到根结点的惟一路径，把到根结点的惟一路径，把到根结点的惟一路径，把到根结点的惟一路径，把HHi i 移到适移到适移到适移到适合它的位置上。在移动的每一步中，将合它的位置上。在移动的每一步中，将合它的位置上。在移动的每一步中，将合它的位置上。在移动的

17、每一步中，将HiHi的键值与它的父结的键值与它的父结的键值与它的父结的键值与它的父结点点点点HH i i/2/2 的键值相比较，若的键值相比较，若的键值相比较，若的键值相比较，若uu若若若若HiHiHH i i/2/2 ，则则则则HiHi和和和和HH i i/2/2 互换（上移），继续互换（上移），继续互换（上移），继续互换（上移），继续。u若若若若HiHHiH i i/2/2 或或或或 i i1 1，终止。，终止。，终止。，终止。11第11页，讲稿共49张，创作于星期日H5=25H5=25H2=17H2=17，互换。互换后，互换。互换后，互换。互换后，互换。互换后H5=17H5=17、H2=

18、25H2=25；H10=25H10=25H5=11H5=11，互换。互换后，互换。互换后，互换。互换后，互换。互换后H10=11H10=11、H5=25H5=25；H10H10的键值由的键值由的键值由的键值由5 5变为变为变为变为25252 20 01 17 79 91 10 01 11 14 45 53 37 72 25 51 12 23 34 45 56 67 78 89 91010H2=25H2=25H1=20H1=20，互换。互换后，互换。互换后，互换。互换后，互换。互换后H2=20H2=20、H1=25H1=25；2 25 52 20 09 91 10 01 17 74 45 53

19、37 71 11 12 20 01 17 79 91 10 02 25 54 45 53 37 71 11 12 20 02 25 59 91 10 01 17 74 45 53 37 71 11 120201 117172 29 910104 411115 55 510104 45 53 37 7H1=25H1=25位于根结点。此时位于根结点。此时位于根结点。此时位于根结点。此时i=1i=1，程序终止。，程序终止。，程序终止。，程序终止。2525101012第12页，讲稿共49张，创作于星期日过程过程 ShiftUp（参见参见Page 75）输入：数组输入：数组H1.n和索引和索引i（1in

20、）输出：上移输出：上移Hi(如果需要如果需要)，使它不大于父结点。，使它不大于父结点。1.1.donefalsedonefalse2.2.if if i i1 then exit1 then exit/根结点根结点根结点根结点3.3.repeatrepeat4.4.if key(H if key(Hi i)key(Hkey(H i i/2/2 )then)then 5.5.互换互换互换互换HHi i 和和和和HH i i/2/2 6.6.else else 7.7.donetruedonetrue8.8.end if end if9.9.i i i i/2/2 10.10.until(unti

21、l(i i=1)or done=1)or done 13第13页，讲稿共49张，创作于星期日ShiftDown 假定对于某个假定对于某个假定对于某个假定对于某个i i n/2n/2 （非叶结点）（非叶结点）（非叶结点）（非叶结点），HHi i 的键值变成小于它的左右的键值变成小于它的左右的键值变成小于它的左右的键值变成小于它的左右子结点子结点子结点子结点H2H2i i 或或或或H2H2i i+1+1 的键值，这样违反了堆的特性，需使用称为的键值，这样违反了堆的特性，需使用称为的键值，这样违反了堆的特性，需使用称为的键值，这样违反了堆的特性，需使用称为ShiftDownShiftDown的运算来

22、修复堆。的运算来修复堆。的运算来修复堆。的运算来修复堆。ShiftDown ShiftDown运算使运算使运算使运算使HHi i 下移到二叉树中适合它的位置上。在下移的每下移到二叉树中适合它的位置上。在下移的每下移到二叉树中适合它的位置上。在下移的每下移到二叉树中适合它的位置上。在下移的每一步中，将一步中，将一步中，将一步中，将HHi i 的键值与它的子结点键值相比较，若的键值与它的子结点键值相比较，若的键值与它的子结点键值相比较，若的键值与它的子结点键值相比较，若uuHHi i 子结点键值子结点键值子结点键值子结点键值，则则则则HHi i 与子结点键值中较大者交换（下移），与子结点键值中较大

23、者交换（下移），与子结点键值中较大者交换（下移），与子结点键值中较大者交换（下移），继续；继续；继续；继续；uuHHi i子结点键值子结点键值子结点键值子结点键值 或或或或 i i n/2n/2 ，终止。，终止。，终止。，终止。说明：说明：说明：说明：HHi i 应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个键值较小的子结点的父结点（如果有的话）。键值较小的子结点的父结点（如果有的话）。键值较小的子结点的父结点

24、（如果有的话）。键值较小的子结点的父结点（如果有的话）。171710101111111110103 33 314第14页，讲稿共49张，创作于星期日说明：若说明：若说明：若说明：若i i n/2n/2 ，则该结点位于叶子的位置，无需下移。，则该结点位于叶子的位置，无需下移。，则该结点位于叶子的位置，无需下移。，则该结点位于叶子的位置，无需下移。n/2n/2 =1515/2/2 =7=7 n/2n/2 =1010/2/2 =5=515第15页，讲稿共49张，创作于星期日H2H2键值由键值由键值由键值由1717变为变为变为变为3 32 20 03 39 91 10 01 11 14 45 53 3

25、7 75 51 12 23 34 45 56 67 78 89 910102 20 01 11 19 91 10 05 54 45 53 37 73 32 20 01 11 19 91 10 03 34 45 53 37 75 5H5=3H5=3小于小于小于小于H10=5H10=5，所以，所以，所以，所以H5H5和和和和H10H10互换。交换后互换。交换后互换。交换后互换。交换后H5=5H5=5，H10=3H10=3；H10=3H10=3位于叶结点位置。位于叶结点位置。位于叶结点位置。位于叶结点位置。i=10i=10 n/2n/2 =5=5，程序终止。，程序终止。，程序终止。，程序终止。H2=

26、3H2=3小于小于小于小于H4H4和和和和H5H5，因为，因为，因为，因为H4H5H4H5，所以，所以，所以，所以H2H2和和和和H5H5互换。交换后互换。交换后互换。交换后互换。交换后H2=11H2=11，H5=3H5=3；20201 117172 29 93 310104 411115 54 45 53 37 75 53 32 216第16页，讲稿共49张，创作于星期日过程过程过程过程 ShiftDownShiftDown（Page 76Page 76）输入：数组输入：数组输入：数组输入：数组H1.nH1.n和索引和索引和索引和索引i i（11i inn）输出：下移输出：下移输出：下移输出

27、：下移HHi i（如果需要），使它不小于子结点。（如果需要），使它不小于子结点。（如果需要），使它不小于子结点。（如果需要），使它不小于子结点。1.1.donefalsedonefalse2.2.if 2if 2i in then exitn then exit/H/Hi i 是叶结点，无需下移。是叶结点，无需下移。是叶结点，无需下移。是叶结点，无需下移。3.3.repeatrepeat4.4.i i22i i /i/i指向子结点指向子结点指向子结点指向子结点5.5.if(if(i i+1n)and(key(H+1n)and(key(Hi i+1)+1)key(Hkey(Hi i)then)t

28、hen6.6.i ii i+1+1 /若有右子结点，选择子结点较大者。若有右子结点，选择子结点较大者。若有右子结点，选择子结点较大者。若有右子结点，选择子结点较大者。7.7.end if end if8.8.if key(H if key(H i i/2/2 )key(H)n)or done n)or done 17第17页，讲稿共49张，创作于星期日插入插入 为了把元素为了把元素为了把元素为了把元素x x插入堆插入堆插入堆插入堆HH中，先将堆的大小增中，先将堆的大小增中，先将堆的大小增中，先将堆的大小增1 1，然后元素，然后元素，然后元素，然后元素x x添添添添加到加到加到加到HH的末尾，再

29、根据需要将的末尾，再根据需要将的末尾，再根据需要将的末尾，再根据需要将x x上移，直到满足堆的特性。若上移，直到满足堆的特性。若上移，直到满足堆的特性。若上移，直到满足堆的特性。若新堆的个数为新堆的个数为新堆的个数为新堆的个数为n n，那么堆树的高度为那么堆树的高度为那么堆树的高度为那么堆树的高度为 log2n 所以将一个元素插入大小为所以将一个元素插入大小为所以将一个元素插入大小为所以将一个元素插入大小为n n的堆中所需要的时间为的堆中所需要的时间为的堆中所需要的时间为的堆中所需要的时间为O(log2n)算法算法4.1 Insert（Page 76-77）输入：堆输入：堆H1.n和元素和元素

30、x输出：新堆输出：新堆H1.n+1，x为其元素之一。为其元素之一。1.nn+12.Hnx3.ShiftUp(H,n)18第18页，讲稿共49张，创作于星期日删除删除 要从大小为要从大小为n的堆中删除元素的堆中删除元素Hi，可先用可先用Hn替换替换Hi，然后将堆的大小减然后将堆的大小减1。设原。设原Hi的键值为的键值为key(x)，原原Hn的键值为的键值为key(y)，若若key(y)key(x)，则执行上移则执行上移y。若若key(y)key(x)，则执行下移则执行下移y。若若i=1，则表示删除堆的最大值。则表示删除堆的最大值。由于堆树的高度为由于堆树的高度为 log2n，所以删除一个元素所所

31、以删除一个元素所需的时间为需的时间为O(log2n)。19第19页，讲稿共49张，创作于星期日算法算法4.2 Delete（Page 77）输入：非空堆输入：非空堆H1.n和索引和索引i（1in）输出：删除输出：删除Hi的新堆的新堆H1.n-11.xHi:yHn/Hi为要删除的元素为要删除的元素2.nn-13.if in+1 then exit/删除堆最后一个元素删除堆最后一个元素4.Hiy5.if key(y)key(x)then6.ShiftUp(H,i)7.else8.ShiftDown(H,i)9.end if20第20页，讲稿共49张，创作于星期日4.2.2 创建堆创建堆方法一方法一

32、 给出有给出有给出有给出有n n个元素的数组个元素的数组个元素的数组个元素的数组A1.nA1.n，要创建一个包含这些元素的堆要创建一个包含这些元素的堆要创建一个包含这些元素的堆要创建一个包含这些元素的堆可以这样进行：可以这样进行：可以这样进行：可以这样进行：首先假设堆由首先假设堆由首先假设堆由首先假设堆由1 1个元素构成，然后将第个元素构成，然后将第个元素构成，然后将第个元素构成，然后将第2 2个、第个、第个、第个、第3 3个元素插入堆，个元素插入堆，个元素插入堆，个元素插入堆，直至直至直至直至n n个。个。个。个。插入第插入第插入第插入第i i个元素，上移次数个元素，上移次数个元素，上移次数

33、个元素，上移次数(循环次数循环次数循环次数循环次数)最多为最多为最多为最多为 loglog2 2i i ，因此，因此，因此，因此采用这种方法创建堆的时间复杂性为采用这种方法创建堆的时间复杂性为采用这种方法创建堆的时间复杂性为采用这种方法创建堆的时间复杂性为O(nlogO(nlog2 2n)n)。算法算法算法算法 MakeHeapByInsertMakeHeapByInsert（参见（参见（参见（参见Page 77Page 77）输入：输入：输入：输入：n n个元素的数组个元素的数组个元素的数组个元素的数组A1.nA1.n输出：堆输出：堆输出：堆输出：堆A1.nA1.n1.1.for for i

34、 i2 to n2 to n2.2.ShiftUp(A,ShiftUp(A,i i)3.3.end forend for21第21页，讲稿共49张，创作于星期日4.15 4.15 给出一个整数数组给出一个整数数组给出一个整数数组给出一个整数数组A1.nA1.n，可按照下面的方法建立一个，可按照下面的方法建立一个，可按照下面的方法建立一个，可按照下面的方法建立一个A A的堆的堆的堆的堆B1.nB1.n。从空堆开始，反复将。从空堆开始，反复将。从空堆开始，反复将。从空堆开始，反复将A A中元素插入中元素插入中元素插入中元素插入B B，每一次调，每一次调，每一次调，每一次调整当时的堆，直到整当时的堆

35、，直到整当时的堆，直到整当时的堆，直到B B包含包含包含包含A A中的所有元素。证明在最坏情况下，中的所有元素。证明在最坏情况下，中的所有元素。证明在最坏情况下，中的所有元素。证明在最坏情况下，算法运行时间是算法运行时间是算法运行时间是算法运行时间是(nlogn)(nlogn)。解：解：解：解：1.1.for for i i1 to n1 to n2.2.BBi iAAi i 3.3.ShiftUp(B,ShiftUp(B,i i)/ShiftUp(B1./ShiftUp(B1.i i,i i)4.4.end forend for在最坏情况下在最坏情况下在最坏情况下在最坏情况下 22第22页，

36、讲稿共49张，创作于星期日4.16 4.16 用用用用图说图说图说图说明明明明练习练习练习练习4.154.15的算法的算法的算法的算法对对对对于下面数于下面数于下面数于下面数组组组组的运算。的运算。的运算。的运算。解：解：解：解：A1.8 A1.8 6 6 9 9 2 2 7 7 1 1 8 8 4 4 3 3B1.1=B1.1=6 66 6 9 99 9 6 69 9 6 6 2 29 9 6 6 2 2 7 79 9 7 7 2 2 6 69 9 7 7 2 2 6 6 1 19 9 7 7 2 2 6 6 1 1 8 89 9 7 7 8 8 6 6 1 1 2 29 9 7 7 8 8

37、 6 6 1 1 2 2 4 49 9 7 7 8 8 6 6 1 1 2 2 4 4 3 3B1.8=B1.8=B1.2=B1.2=B1.3=B1.3=B1.4=B1.4=B1.5=B1.5=B1.7=B1.7=B1.6=B1.6=23第23页，讲稿共49张，创作于星期日方法二方法二方法二方法二 设数组设数组设数组设数组A A有有有有n=10n=10个元素，构造它的几乎完全二叉树个元素，构造它的几乎完全二叉树个元素，构造它的几乎完全二叉树个元素，构造它的几乎完全二叉树T T，如，如，如，如下所示，显然下所示，显然下所示，显然下所示，显然T T不是堆。不是堆。不是堆。不是堆。4 43 38 8

38、1010111113137 73030171726261 12 23 34 45 56 67 78 89 91010 观察数组观察数组观察数组观察数组A A的元素：的元素：的元素：的元素：AA n/2n/2 +1+1=A6=A6，AAn n=A10=A10，它们对应于，它们对应于，它们对应于，它们对应于T T的叶子。这样调整可以从内部结点开始，先调整的叶子。这样调整可以从内部结点开始，先调整的叶子。这样调整可以从内部结点开始，先调整的叶子。这样调整可以从内部结点开始，先调整AA n/2n/2 =A=A5 5，随后随后随后随后调整调整调整调整AA n/2n/2 -1-1=A=A4 4 ，直至直至

39、直至直至AA1 1。4 41 13 32 28 83 310104 411115 513136 67 77 730308 817179 92626101024第24页，讲稿共49张，创作于星期日 4 41 1 3 32 2 8 83 3 10 104 4 11 115 513136 6 7 77 730308 8 17 179 9 26 2610104 43 38 81010111113137 73030171726261 12 23 34 45 56 67 78 89 91010AA n/2n/2 =A5=11=A5=11AA n/2n/2 -1=A4=10-1=A4=10AA n/2n/2

40、 -2=A3=8-2=A3=8AA n/2n/2 -3-3=A2=3=A2=3 AA n/2n/2 -4-4=A1=4=A1=44 43 38 81010262613137 73030171711114 43 38 83030262613137 71010171711114 43 31313303026268 87 71010171711114 4303013133 326268 87 71010171711114 430301313171726268 87 710103 3111130304 41313171726268 87 710103 3111130302626131317174 48

41、 87 710103 31111303026261313171711118 87 710103 34 425第25页，讲稿共49张，创作于星期日算法算法 MakeHeap(Page 79)输入：输入：n个元素的数组个元素的数组A1.n输出：堆输出：堆A1.n1.for i n/2 downto 12.ShiftDown(A,i)3.end for 设树设树T的高度为的高度为k=log2n，令令Aj为对应于树的第为对应于树的第i层层中的第中的第j个结点，执行个结点，执行ShiftDown(A,j)运算，下移次数运算，下移次数(即循环次数即循环次数)最多为最多为k-i。因为在第因为在第i层恰好有层

42、恰好有2i个结点，个结点，故执行总的下移次数的上界为：故执行总的下移次数的上界为：20(k-0)+21(k-1)+22(k-2)+2k-3(3)+2k-2(2)+2k-1(1)26第26页，讲稿共49张，创作于星期日 第第第第0 0层结点下移最多次数层结点下移最多次数层结点下移最多次数层结点下移最多次数2 20 0(k-0)(k-0)令令令令k=k=loglog2 2n n ，设，设，设，设n=31n=31则则则则k=4k=4。第第第第1 1层结点下移最多次数层结点下移最多次数层结点下移最多次数层结点下移最多次数2 21 1(k-1)(k-1)第第第第i i层结点下移最多次数层结点下移最多次数

43、层结点下移最多次数层结点下移最多次数2 2i i(k-(k-i i)第第第第k-1k-1层结点下移最多次数层结点下移最多次数层结点下移最多次数层结点下移最多次数2 2k-1k-1(k-(k-1)=2(k-(k-1)=2k-1k-1(1)(1)设树设树设树设树T T的高度为的高度为的高度为的高度为k k loglog2 2n n ，令令令令AAj j 为对应于树的第为对应于树的第为对应于树的第为对应于树的第i i层中的第层中的第层中的第层中的第j j个结点，个结点，个结点，个结点，执行执行执行执行ShiftDown(A,ShiftDown(A,j j)运算，下移次数运算，下移次数运算，下移次数运

44、算，下移次数(即循环次数即循环次数即循环次数即循环次数)最多为最多为最多为最多为k-k-i i。因为在第因为在第因为在第因为在第i i层恰好有层恰好有层恰好有层恰好有2 2i i个结点，故执行总的下移次数的上界为个结点，故执行总的下移次数的上界为个结点，故执行总的下移次数的上界为个结点，故执行总的下移次数的上界为:2 20 0(k-0)+2k-0)+21 1(k-1)+2(k-1)+22 2(k-2)+2(k-2)+2k-3k-3(3)+2(3)+2k-2k-2(2)+2(2)+2k-1k-1(1)(1)第第第第2 2层结点下移最多次数层结点下移最多次数层结点下移最多次数层结点下移最多次数2

45、22 2(k-2)(k-2)27第27页，讲稿共49张，创作于星期日可参考本书可参考本书可参考本书可参考本书 Page 50Page 50（式（式（式（式2.142.14）28第28页，讲稿共49张，创作于星期日定理定理4.1（Page 79）使用算法使用算法MakeHeap构造一个构造一个n元素的堆，令元素的堆，令C(n)为执行该算法的元素比较次数，那么为执行该算法的元素比较次数，那么n-1C(n)4n因此构造一个因此构造一个n个元素的堆，算法个元素的堆，算法MakeHeap需要需要(n)时间和时间和(1)空间。空间。在过程在过程在过程在过程ShiftDownShiftDown的每一次循环中

46、，最多有二次元素比较（有的每一次循环中，最多有二次元素比较（有的每一次循环中，最多有二次元素比较（有的每一次循环中，最多有二次元素比较（有二个二个二个二个if if语句），因此元素总的比较次数上界为语句），因此元素总的比较次数上界为语句），因此元素总的比较次数上界为语句），因此元素总的比较次数上界为2*2n2*2n。同时过程。同时过程。同时过程。同时过程ShiftDownShiftDown至少执行一次循环，所以元素的最少比较次数由内至少执行一次循环，所以元素的最少比较次数由内至少执行一次循环，所以元素的最少比较次数由内至少执行一次循环，所以元素的最少比较次数由内部结点数决定，元素总的比较次数下

47、界为部结点数决定，元素总的比较次数下界为部结点数决定，元素总的比较次数下界为部结点数决定，元素总的比较次数下界为2 2 n/2n/2 n-1n-1（若原为（若原为（若原为（若原为堆）。堆）。堆）。堆）。29第29页，讲稿共49张，创作于星期日4.2.3 堆排序堆排序 给定数组给定数组给定数组给定数组A1.nA1.n，设每个元素的键值是该元素本身，可采设每个元素的键值是该元素本身，可采设每个元素的键值是该元素本身，可采设每个元素的键值是该元素本身，可采用如下方法进行排序：用如下方法进行排序：用如下方法进行排序：用如下方法进行排序：uu使用算法使用算法使用算法使用算法MakeHeapMakeHea

48、p将数组将数组将数组将数组A A变换成堆。变换成堆。变换成堆。变换成堆。uu首先将首先将首先将首先将A1A1和和和和AnAn交换，显然交换，显然交换，显然交换，显然AnAn为数组中最大元素，为数组中最大元素，为数组中最大元素，为数组中最大元素，然后调用过程然后调用过程然后调用过程然后调用过程ShiftDownShiftDown将将将将A1.A1.n-1n-1 转换成堆。转换成堆。转换成堆。转换成堆。uu接着将接着将接着将接着将A1A1和和和和An-1An-1交换，显然交换，显然交换，显然交换，显然An-1An-1为数组中次最大为数组中次最大为数组中次最大为数组中次最大元素，然后调用过程元素，然

49、后调用过程元素，然后调用过程元素，然后调用过程ShiftDownShiftDown将将将将A1.A1.n-2n-2 转换成堆。转换成堆。转换成堆。转换成堆。uu交换元素和堆调整过程一直重复，直至堆的大小为交换元素和堆调整过程一直重复，直至堆的大小为交换元素和堆调整过程一直重复，直至堆的大小为交换元素和堆调整过程一直重复，直至堆的大小为1 1。30第30页，讲稿共49张，创作于星期日算法算法4.5 HeapSort(Page 80)输入：输入：n个元素的数组个元素的数组A输出：数组输出：数组A中元素按升序排列中元素按升序排列1.MakeHeap(A)2.for jn downto 23.互换互换

50、A1和和Aj4.ShiftDown(A1.j-1,1)5.end for 这个算法在原有空间进行排序，建立堆用这个算法在原有空间进行排序，建立堆用(n)时时间，间，ShiftDown运算用运算用O(log2n)时间，并且重复时间，并且重复n-1次。次。参考习题参考习题4.1431第31页，讲稿共49张，创作于星期日 这个算法在原有空间进行排序，建立堆用这个算法在原有空间进行排序，建立堆用(n)时时间，间，ShiftDown运算用运算用O(log2n)时间，并且重复时间，并且重复n-1次，次，显然建立堆所用的时间为低次项，可略。显然建立堆所用的时间为低次项，可略。定理定理4.2(Page 80)