堆和不相交数据结构.ppt

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

1、堆和不相交数据结构现在学习的是第1页，共49页二叉树性质二叉树性质二叉树性质二叉树性质 (Page 71)(Page 71)性质性质1：在二叉树中，第：在二叉树中，第：在二叉树中，第：在二叉树中，第j j层的顶点数最多是层的顶点数最多是2j j。性质性质2：令二叉树：令二叉树T顶点数是顶点数是n，高度是，高度是，高度是，高度是k k，那么，那么，那么，那么如果如果T是完全的，等号成立。如果是完全的，等号成立。如果T是几乎完全的，那么是几乎完全的，那么是几乎完全的，那么是几乎完全的，那么性质性质3 3：有：有：有：有n个顶点的完全或几乎完全的二叉树的高度是个顶点的完全或几乎完全的二叉树的高度是个

2、顶点的完全或几乎完全的二叉树的高度是个顶点的完全或几乎完全的二叉树的高度是性质性质4 4：对任何一棵二叉树：对任何一棵二叉树T T，如果其终端结点数为如果其终端结点数为n0n0，度为度为2 2的的结点数为结点数为n2n2，则则n0=n2+1n0=n2+12现在学习的是第2页，共49页性质：对任何一棵二叉树性质：对任何一棵二叉树T T，如果其终端结点数为如果其终端结点数为n0n0，度为度为2 2的结点数为的结点数为n2n2，则则n0=n2+1n0=n2+1证明：证明：n1为二叉树为二叉树T中度为中度为1的结点数的结点数 因为：二叉树中所有结点的度均小于或等于因为：二叉树中所有结点的度均小于或等于

3、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页性质性质5：如果对一棵有：如果对一棵有：如果对一棵有：如果对一棵有n n个结点的完全二叉树的结点按层序编个结点的完全二叉树的结点按层序编号，则对任一结点号，则对任一结点i(1 i n)，有：，有：(1)(

4、1)如果如果如果如果i=1，则结点，则结点，则结点，则结点i是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果i1，则，则，则，则其双亲是其双亲是其双亲是其双亲是 i/2 (2)(2)如果如果如果如果2in，则结点，则结点，则结点，则结点i i无左孩子；如果无左孩子；如果无左孩子；如果无左孩子；如果2i n，则其左孩子是，则其左孩子是2i (3)如果如果2i+1n2i+1n，则结点，则结点，则结点，则结点i i无右孩子；如果无右孩子；如果无右孩子；如果无右孩子；如果2i+1 n，则其右，则其右孩子是孩子是2i+14现在学习的是第4页，共49

5、页4.1 引言（堆、不相交集）引言（堆、不相交集）4.2 堆堆 4.2.1 堆上的运算堆上的运算 4.2.2 创建堆创建堆 4.2.3 堆排序堆排序 4.2.4 最大堆和最小堆最大堆和最小堆4.3 不相交集数据结构不相交集数据结构 4.3.1 按秩合并措施按秩合并措施 4.3.3 Union-Find算法算法 4.3.2 路径压缩路径压缩 4.3.4 Union-Find算法的分析（略）算法的分析（略）5现在学习的是第5页，共49页4.2 堆堆堆的引入堆的引入在许多算法中，需要支持下面二种运算：在许多算法中，需要支持下面二种运算：在许多算法中，需要支持下面二种运算：在许多算法中，需要支持下面二

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

7、素。很多元素。很多元素。使用堆，寻找最大值元素容易，插入操作仅需移动少量使用堆，寻找最大值元素容易，插入操作仅需移动少量使用堆，寻找最大值元素容易，插入操作仅需移动少量使用堆，寻找最大值元素容易，插入操作仅需移动少量元素。元素。元素。元素。6现在学习的是第6页，共49页定义定义4.1（Page 74）一个（二叉）堆是一棵几乎完全的二叉树，它的一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设每个结点都满足堆的特性：设v是一个结点，是一个结点，p(v)是是v的父结点，那么存储在的父结点，那么存储在p(v)中的数据项键值大于或中的数据项键值大于或等于存储在等于存储在v中的数据项键

8、值。中的数据项键值。堆的定义（二叉堆）堆的定义（二叉堆）几乎完全二叉树（几乎完全二叉树（几乎完全二叉树（几乎完全二叉树（Page 71Page 71）如果一棵二叉树，除了如果一棵二叉树，除了如果一棵二叉树，除了如果一棵二叉树，除了最右边最右边最右边最右边位置位置位置位置上的一个或几个上的一个或几个上的一个或几个上的一个或几个叶子叶子叶子叶子可能缺少外，它可能缺少外，它可能缺少外，它可能缺少外，它是丰满的，我们定义它为几乎完全二是丰满的，我们定义它为几乎完全二是丰满的，我们定义它为几乎完全二是丰满的，我们定义它为几乎完全二叉树。叉树。叉树。叉树。几乎完全二叉树例几乎完全二叉树例几乎完全二叉树例几

9、乎完全二叉树例7现在学习的是第7页，共49页堆数据结构支持下列运算堆数据结构支持下列运算uDeleteMax(H)：从一个非空堆：从一个非空堆H中，删除最大键中，删除最大键值的数据项，并返回该数据；值的数据项，并返回该数据；uInsert(H,x)：将数据项：将数据项x插入堆插入堆H中；中；uDelete(H,i)：从堆中删除第：从堆中删除第i项；项；uMakeHeap(A)：将数组转换为堆。：将数组转换为堆。堆的蕴含特性：堆的蕴含特性：沿着每条从根到叶子的路径，元素的键值以降序沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。（或称非升序）排列。8现在学习的是第8页，共49页堆的

10、表示堆的表示 有有n个结点堆个结点堆T，可以用一个数组，可以用一个数组H1.nH1.n用下面方式来表用下面方式来表示：示：uT的根结点存储在的根结点存储在的根结点存储在的根结点存储在H1中；中；中；中；uu设设设设T T的结点存储在的结点存储在的结点存储在的结点存储在HHj 中，如果它有左子结点，则这个中，如果它有左子结点，则这个左子结点存储在左子结点存储在H2H2j中。如果它还有右子结点，这个右中。如果它还有右子结点，这个右子结点存储在子结点存储在H2H2j+1；u若元素若元素Hj 不是根结点，它的父结点存储在不是根结点，它的父结点存储在H j/2/2 中。中。由由由由“几乎完全二叉树几乎完

11、全二叉树几乎完全二叉树几乎完全二叉树”的定义可知，如果堆中某结点有右子的定义可知，如果堆中某结点有右子的定义可知，如果堆中某结点有右子的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。结点，则它一定也有左子结点。结点，则它一定也有左子结点。结点，则它一定也有左子结点。堆具有如下性质：堆具有如下性质：堆具有如下性质：堆具有如下性质：key(Hkey(H j/2 )key(Hj)2 j jnn9现在学习的是第9页，共49页2011729310411546573879510堆和它的数组表示法堆和它的数组表示法 把存储在堆中的数据项视为键值。按树的结点把存储在堆中的数据项视为键值。按树的结点

12、把存储在堆中的数据项视为键值。按树的结点把存储在堆中的数据项视为键值。按树的结点“自顶向下自顶向下自顶向下自顶向下”、“从左至右从左至右从左至右从左至右”、“按按按按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的的的的左子结点左子结点左子结点

13、左子结点为为为为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 假定对于某个假定对于某个假定对于某个假定对于某个i1，Hi的键值变成大于它父结点的键值，的键值变成大于它父结点的键值，这样违反了堆的特性，需使用称

14、为这样违反了堆的特性，需使用称为ShiftUpShiftUp的运算来修复堆。的运算来修复堆。的运算来修复堆。的运算来修复堆。ShiftUp运算沿着从运算沿着从HHi i 到根结点的惟一路径，把到根结点的惟一路径，把Hi移到移到适合它的位置上。在移动的每一步中，将适合它的位置上。在移动的每一步中，将HiHi的键值与它的的键值与它的父结点父结点H i i/2/2 的键值相比较，若的键值相比较，若uu若若若若HiHiH i i/2 ，则则则则HiHi和和H i/2/2 互换（上移），继续互换（上移），继续互换（上移），继续互换（上移），继续。uu若若若若HiHHiH i/2/2 或或 i1，终止。，

15、终止。，终止。，终止。11现在学习的是第11页，共49页H5=25H5=25H2=17H2=17，互换。互换后，互换。互换后，互换。互换后，互换。互换后H5=17H5=17、H2=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=20

16、H1=20，互换。互换后，互换。互换后，互换。互换后，互换。互换后H2=20H2=20、H1=25H1=25；2 25 52 20 09 91 10 01 17 74 45 53 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 1201171729104 411115 55101045 537H1=25H1=25位于根结点。此时位于根结点。此时位于根结点。此时位于根结点。此时i=1i=1，程序终止。，程序终止。，程序终止。，程序终止。251012

17、现在学习的是第12页，共49页过程过程 ShiftUp（参见参见Page 75）输入：数组输入：数组H1.n和索引和索引i（1in）输出：上移输出：上移Hi(如果需要如果需要)，使它不大于父结点。，使它不大于父结点。1.1.donefalsedonefalse2.if i1 then exit/根结点根结点3.3.repeatrepeat4.if key(Hi i)key(H i i/2)then 5.互换互换HHi i 和和和和HH i i/2/2 6.else 7.donetrue8.8.end if end if9.i i i/2 10.10.until(until(i=1)or don

18、e 13现在学习的是第13页，共49页ShiftDown 假定对于某个假定对于某个假定对于某个假定对于某个i i n/2n/2 （非叶结点）（非叶结点）（非叶结点）（非叶结点），HHi i 的键值变成小于它的左右子的键值变成小于它的左右子的键值变成小于它的左右子的键值变成小于它的左右子结点结点结点结点H2H2i i 或或或或H2H2i i+1+1 的键值，这样违反了堆的特性，需使用称为的键值，这样违反了堆的特性，需使用称为的键值，这样违反了堆的特性，需使用称为的键值，这样违反了堆的特性，需使用称为ShiftDownShiftDown的运算来修复堆。的运算来修复堆。的运算来修复堆。的运算来修复堆

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

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

21、。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页H2键值由键值由键值由键值由1717变为变为变为变为32 20 03 39 91 10 01 11 14 45 53 37 75 51 12 23 34 45 56 67 78 89 91010

22、2 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=3H2=3小于小于小于小于H4H4和和和和H5H5，因为，因为，因为，因为

23、H4H5H4H5，所以，所以，所以，所以H2H2和和和和H5H5互换。交换后互换。交换后互换。交换后互换。交换后H2=11H2=11，H5=3H5=3；20201 1172 293 3104 411115 545 537 753 32 216现在学习的是第16页，共49页过程过程过程过程 ShiftDown（Page 76）输入：数组输入：数组输入：数组输入：数组H1.nH1.n和索引和索引和索引和索引i i（11in）输出：下移输出：下移HHi（如果需要），使它不小于子结点。（如果需要），使它不小于子结点。（如果需要），使它不小于子结点。（如果需要），使它不小于子结点。1.1.donefal

24、sedonefalse2.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)then6.6.i ii i+1+1 /若有右子结点，选择子结点较大者。若有右子结点，选择子结点较大者。若有右子结点，选择子结点较大者。若有右子结点，选择子结点较大者。

25、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插入堆插入堆插入堆插入堆H中，先将堆的大小增中，先将堆的大小增1，然后元素，然后元素x x添添加到加到HH的末尾，再根据需要将的末尾，再根据需要将x x上移，直到满足堆的特性。上移，直到满足堆的特性。若新堆的个数为若新堆的个数为n，那么堆树的高度为那么堆树的高度为那么堆树的高度为那么堆树的高度为 log2n 所以将一个元素插入大小为所以将一个元素插入大小为所以将一

26、个元素插入大小为所以将一个元素插入大小为n n的堆中所需要的时间为的堆中所需要的时间为O(log2n)算法算法4.1 Insert（Page 76-77）输入：堆输入：堆H1.n和元素和元素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)，则执行上移则执行

27、上移y。若若key(y)key(x)，则执行下移则执行下移y。若若i=1，则表示删除堆的最大值。则表示删除堆的最大值。由于堆树的高度为由于堆树的高度为 log2n，所以删除一个元素所以删除一个元素所需的时间为所需的时间为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

28、(x)then6.ShiftUp(H,i)7.else8.ShiftDown(H,i)9.end if20现在学习的是第20页，共49页4.2.2 创建堆创建堆方法一方法一 给出有给出有给出有给出有n个元素的数组个元素的数组个元素的数组个元素的数组A1.nA1.n，要创建一个包含这些元素的要创建一个包含这些元素的要创建一个包含这些元素的要创建一个包含这些元素的堆可以这样进行：堆可以这样进行：堆可以这样进行：堆可以这样进行：首先假设堆由首先假设堆由1个元素构成，然后将第个元素构成，然后将第2个、第个、第3个元素个元素插入堆，直至插入堆，直至n n个。个。个。个。插入第插入第插入第插入第i i个元

29、素，上移次数个元素，上移次数个元素，上移次数个元素，上移次数(循环次数循环次数循环次数循环次数)最多为最多为最多为最多为 loglog2i i，因此采，因此采，因此采，因此采用这种方法创建堆的时间复杂性为用这种方法创建堆的时间复杂性为用这种方法创建堆的时间复杂性为用这种方法创建堆的时间复杂性为O(nlogO(nlog2n)。算法算法 MakeHeapByInsert（参见（参见（参见（参见Page 77）输入：输入：输入：输入：n个元素的数组个元素的数组个元素的数组个元素的数组A1.n输出：堆输出：堆输出：堆输出：堆A1.n1.for i2 to n2.2.ShiftUp(A,ShiftUp(

30、A,i)3.3.end forend for21现在学习的是第21页，共49页4.15 4.15 给出一个整数数组给出一个整数数组A1.n，可按照下面的方法建立一个，可按照下面的方法建立一个，可按照下面的方法建立一个，可按照下面的方法建立一个A A的堆的堆的堆的堆B1.n。从空堆开始，反复将。从空堆开始，反复将A中元素插入中元素插入中元素插入中元素插入B B，每一次调，每一次调整当时的堆，直到整当时的堆，直到B B包含包含A中的所有元素。证明在最坏情况中的所有元素。证明在最坏情况下，算法运行时间是下，算法运行时间是(nlogn)(nlogn)。解：解：1.1.for for i i1 to n

31、2.2.BBiAAi3.3.ShiftUp(B,ShiftUp(B,i)/ShiftUp(B1.i,i i)4.4.end forend for在最坏情况下在最坏情况下 22现在学习的是第22页，共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

32、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 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个元素，构造它的几乎完全二叉树个元素，构造它的几乎完全二叉树个元素，构造它的几乎完全二

33、叉树个元素，构造它的几乎完全二叉树T T，如，如，如，如下所示，显然下所示，显然下所示，显然下所示，显然T T不是堆。不是堆。不是堆。不是堆。4 43 38 81010111113137 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的叶子。这样调整可以从内部结点开始，先调整的叶子。这样调整可以从内部结点开始，先调整的叶子。这样调整可以从内部结点开始，先调整的叶

34、子。这样调整可以从内部结点开始，先调整AA n/2n/2 =A=A5 5，随后调整随后调整随后调整随后调整AA n/2n/2 -1-1=A=A4 4 ，直至直至直至直至AA1 1。4 41 13283 3104 4115 5131367 77 730817179261024现在学习的是第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

35、 n/2n/2 =A5=11=A5=11AA n/2n/2 -1=A4=10-1=A4=10AA n/2n/2 -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 311113

36、0304 41313171726268 87 710103 3111130302626131317174 48 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,

37、j)运算，下移次运算，下移次数数(即循环次数即循环次数)最多为最多为k-i。因为在第因为在第i层恰好有层恰好有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层结点下移最多次数层结点下移最多次数层结点下移最多次数层

38、结点下移最多次数2 21 1(k-1)(k-1)第第第第i i层结点下移最多次数层结点下移最多次数层结点下移最多次数层结点下移最多次数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个结点，个结点，个结点，个结点，执行执行执行执行S

39、hiftDown(A,ShiftDown(A,j j)运算，下移次数运算，下移次数运算，下移次数运算，下移次数(即循环次数即循环次数即循环次数即循环次数)最多为最多为最多为最多为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

40、)(1)第第第第2 2层结点下移最多次数层结点下移最多次数层结点下移最多次数层结点下移最多次数2 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)空间。空

41、间。在过程在过程在过程在过程ShiftDown的每一次循环中，最多有二次元素比较的每一次循环中，最多有二次元素比较的每一次循环中，最多有二次元素比较的每一次循环中，最多有二次元素比较（有二个（有二个（有二个（有二个if语句），因此元素总的比较次数上界为语句），因此元素总的比较次数上界为语句），因此元素总的比较次数上界为语句），因此元素总的比较次数上界为2*2n2*2n。同时过。同时过。同时过。同时过程程程程ShiftDown至少执行一次循环，所以元素的最少比较次数由内至少执行一次循环，所以元素的最少比较次数由内至少执行一次循环，所以元素的最少比较次数由内至少执行一次循环，所以元素的最少比较次数

42、由内部结点数决定，元素总的比较次数下界为部结点数决定，元素总的比较次数下界为部结点数决定，元素总的比较次数下界为部结点数决定，元素总的比较次数下界为2 2 n/2n/2 n-1（若原为堆）（若原为堆）（若原为堆）（若原为堆）。29现在学习的是第29页，共49页4.2.3 堆排序堆排序 给定数组给定数组给定数组给定数组A1.nA1.n，设每个元素的键值是该元素本身，可采设每个元素的键值是该元素本身，可采用如下方法进行排序：用如下方法进行排序：u使用算法使用算法MakeHeapMakeHeap将数组将数组将数组将数组A A变换成堆。变换成堆。变换成堆。变换成堆。u首先将首先将A1和和和和An交换，

43、显然交换，显然An为数组中最大元素，为数组中最大元素，然后调用过程然后调用过程ShiftDownShiftDown将将将将A1.A1.n-1转换成堆。转换成堆。uu接着将接着将接着将接着将A1A1和和An-1An-1交换，显然交换，显然An-1An-1为数组中次最大为数组中次最大元素，然后调用过程元素，然后调用过程ShiftDown将将将将A1.n-2n-2转换成堆。转换成堆。u交换元素和堆调整过程一直重复，直至堆的大小为交换元素和堆调整过程一直重复，直至堆的大小为1。30现在学习的是第30页，共49页算法算法4.5 HeapSort(Page 80)输入：输入：n个元素的数组个元素的数组A输

44、出：数组输出：数组A中元素按升序排列中元素按升序排列1.MakeHeap(A)2.for jn downto 23.互换互换A1和和Aj4.ShiftDown(A1.j-1,1)5.end for 这个算法在原有空间进行排序，建立堆用这个算法在原有空间进行排序，建立堆用(n)时时间，间，ShiftDown运算用运算用O(log2n)时间，并且重复时间，并且重复n-1次。次。参考习题参考习题4.1431现在学习的是第31页，共49页 这个算法在原有空间进行排序，建立堆用这个算法在原有空间进行排序，建立堆用(n)时时间，间，ShiftDown运算用运算用O(log2n)时间，并且重复时间，并且重复

45、n-1次，次，显然建立堆所用的时间为低次项，可略。显然建立堆所用的时间为低次项，可略。定理定理4.2(Page 80)算法算法HeapSort对对n个元素排序，需要用个元素排序，需要用O(nlog2n)时间和时间和(1)空间。空间。由此可见，堆排序是最优秀的排序算法。由此可见，堆排序是最优秀的排序算法。4.2.4 最大堆和最小堆最大堆和最小堆 最大堆：最大键值元素存放在根结点。最大堆：最大键值元素存放在根结点。最小堆：最小键值元素存放在根结点。最小堆：最小键值元素存放在根结点。32现在学习的是第32页，共49页4.3 不相交集数据结构不相交集数据结构（并查集）并查集）是一种树型的数据结构，用于

46、处理一些不相交集合是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。如数据结构课中讲到的最）的合并及查询问题。如数据结构课中讲到的最小生成树小生成树Kruskal算法：算法：Kruskal是一种贪心算法，比较适用于稀疏图是一种贪心算法，比较适用于稀疏图:为使生成树为使生成树上边的权值和最小，则应使生成树中每一条边的权值尽可上边的权值和最小，则应使生成树中每一条边的权值尽可能地小。能地小。具体做法具体做法:找出森林中连接任意两棵树的所有边中，具有最小找出森林中连接任意两棵树的所有边中，具有最小权值的边，如果将它加入生成树中不产生回路，则它就是生成权值的边

47、，如果将它加入生成树中不产生回路，则它就是生成树中的一条边。这里的关键就是如何判断树中的一条边。这里的关键就是如何判断将它加入生成树中将它加入生成树中不产生回路不产生回路。33现在学习的是第33页，共49页4.3 不相交集数据结构不相交集数据结构不相交集合及运算不相交集合及运算 设集合设集合设集合设集合S S有有有有n n个元素，这些元素被分成若干个不相交子集。最初假设个元素，这些元素被分成若干个不相交子集。最初假设个元素，这些元素被分成若干个不相交子集。最初假设个元素，这些元素被分成若干个不相交子集。最初假设每个元素自成一个集合，这样共有每个元素自成一个集合，这样共有每个元素自成一个集合，这

48、样共有每个元素自成一个集合，这样共有n n个子集。经个子集。经个子集。经个子集。经n n次合并（次合并（次合并（次合并（UnionUnion）后，）后，）后，）后，构成若干个不相交子集。每个子集用该子集中一个特殊元素命名。构成若干个不相交子集。每个子集用该子集中一个特殊元素命名。构成若干个不相交子集。每个子集用该子集中一个特殊元素命名。构成若干个不相交子集。每个子集用该子集中一个特殊元素命名。例：假定例：假定例：假定例：假定n n个元素的集合个元素的集合个元素的集合个元素的集合S=1,2,3,4,5,6,7,8,9,10,11S=1,2,3,4,5,6,7,8,9,10,11 最初有最初有最初

49、有最初有1111个子集个子集个子集个子集1,2,3,4,5,6,7,8,9,10,111,2,3,4,5,6,7,8,9,10,11 每个子集的名称分别为子集中元素本身。每个子集的名称分别为子集中元素本身。每个子集的名称分别为子集中元素本身。每个子集的名称分别为子集中元素本身。经若干次合并后，形成经若干次合并后，形成经若干次合并后，形成经若干次合并后，形成4 4个子集，假设它们是个子集，假设它们是个子集，假设它们是个子集，假设它们是1,7,10,11,2,3,5,6,4,8,91,7,10,11,2,3,5,6,4,8,9 4 4个子集依次被命名为个子集依次被命名为个子集依次被命名为个子集依次

50、被命名为1 1、3 3、8 8、9 9。34现在学习的是第34页，共49页 我们对我们对Union和和Find二种不相集运算定义如下：二种不相集运算定义如下：uFind(x)：寻找并返回包含元素：寻找并返回包含元素x的集合名字。的集合名字。uUnion(x,y)：将包含元素：将包含元素x和和y的二个集合用它们的二个集合用它们的并集替换。并集的名字，或为包含元素的并集替换。并集的名字，或为包含元素x的那的那个集合的名字，或为包含元素个集合的名字，或为包含元素y的那个集合的名字。的那个集合的名字。我们目的是设计这二种运算的有效算法，为此需要我们目的是设计这二种运算的有效算法，为此需要一种数据结构，