堆与不相交数据结构.ppt

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

1、堆和不相交数据结构第一张，PPT共四十九页，创作于2022年6月二叉树性质二叉树性质 (Page 71)(Page 71)性质性质1 1：在二叉树中，第：在二叉树中，第j j层的顶点数最多是层的顶点数最多是2 2j j。性质性质2 2：令二叉树：令二叉树T T顶点数是顶点数是n n，高度是，高度是k k，那么，那么如果如果T T是完全的，等号成立。如果是完全的，等号成立。如果T T是几乎完全的，那么是几乎完全的，那么性质性质3 3：有：有n n个顶点的完全或几乎完全的二叉树的高度是个顶点的完全或几乎完全的二叉树的高度是性质4：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则

2、n0=n2+1第二张，PPT共四十九页，创作于2022年6月2性质：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=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第三张，PPT共四十九页，创作于2022年6月性质性质5 5：如果对一棵有：如果对一棵有n n个结点的完全二叉树的结点按层序编

3、号，个结点的完全二叉树的结点按层序编号，则对任一结点则对任一结点i(1in)，有：，有：(1)(1)如果如果i=1i=1，则结点，则结点i i是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果i1i1，则，则其双亲是其双亲是i/2 (2)(2)如果如果2in2in，则结点，则结点i i无左孩子；如果无左孩子；如果2in，则其左孩子，则其左孩子是是2i2i (3)(3)如果如果2i+1n2i+1n，则结点，则结点i i无右孩子；如果无右孩子；如果2i+1n，则其右，则其右孩子是孩子是2i+12i+1第四张，PPT共四十九页，创作于2022年6月44.1 引言（堆、不相交集）引言（堆、不相交集）

4、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算法的分析（略）算法的分析（略）第五张，PPT共四十九页，创作于2022年6月54.2 堆堆堆的引入堆的引入在许多算法中，需要支持下面二种运算：在许多算法中，需要支持下面二种运算：在许多算法中，需要支持下面二种运算：在许多算法中，需要支持下面二种运算：u插入元素插入元素u寻找

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

6、堆，寻找最大值元素容易，插入操作仅需移动少量元素。少量元素。第六张，PPT共四十九页，创作于2022年6月6定义4.1（Page 74）一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设v是一个结点，p(v)是v的父结点，那么存储在p(v)中的数据项键值大于或等于存储在v中的数据项键值。堆的定义（二叉堆）几乎完全二叉树（几乎完全二叉树（Page 71Page 71）如果一棵二叉树，除了如果一棵二叉树，除了最右边最右边位置上位置上的一个或几个的一个或几个叶子叶子可能缺少外，它是丰可能缺少外，它是丰满的，我们定义它为几乎完全二叉树。满的，我们定义它为几乎完全二叉树。几乎完全二叉树

7、例几乎完全二叉树例第七张，PPT共四十九页，创作于2022年6月7堆数据结构支持下列运算uDeleteMax(H)：从一个非空堆H中，删除最大键值的数据项，并返回该数据；uInsert(H,x)：将数据项x插入堆H中；uDelete(H,i)：从堆中删除第i项；uMakeHeap(A)：将数组转换为堆。堆的蕴含特性：沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。第八张，PPT共四十九页，创作于2022年6月8堆的表示 有有n n个结点堆个结点堆T T，可以用一个数组，可以用一个数组H1.nH1.n用下面方式来表示：用下面方式来表示：uuT T的根结点存储在的根结点存储在H1H1

8、中；中；uu设设T T的结点存储在的结点存储在HHj j 中，如果它有左子结点，则这个左中，如果它有左子结点，则这个左子结点存储在子结点存储在H2H2j j 中。如果它还有右子结点，这个右子结点存中。如果它还有右子结点，这个右子结点存储在储在H2H2j j+1+1；uu若元素若元素HHj j 不是根结点，它的父结点存储在不是根结点，它的父结点存储在HH j j/2/2 中。中。由由“几乎完全二叉树几乎完全二叉树”的定义可知，如果堆中某结点有右子结的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。点，则它一定也有左子结点。堆具有如下性质：堆具有如下性质：key(Hkey(H j j/2

9、/2)key(H)key(Hj j)2 2 j jnn第九张，PPT共四十九页，创作于2022年6月92011729310411546573879510堆和它的数组表示法堆和它的数组表示法 把存储在堆中的数据项视为键值。按树的结点把存储在堆中的数据项视为键值。按树的结点“自顶向下自顶向下”、“从左至右从左至右”、“按按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 91010H

10、2=17H2=17的的左子结点左子结点为为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 沿着每条从根到叶子沿着每条从根到叶子的路径，元素的键值以的路径，元素的键值以降序排列。降序排列。第十张，PPT共四十九页，创作于2022年6月104.2.1 堆上的运算堆上的运算ShiftUp 假定对于某个假定对于某个i i1 1，HHi i 的键值变成大于它父结点的键值，这的键值变成大于它父结点的键值，这样违反了堆的特性，需使用称为样违反

11、了堆的特性，需使用称为ShiftUpShiftUp的运算来修复堆。的运算来修复堆。ShiftUpShiftUp运算沿着从运算沿着从HHi i 到根结点的惟一路径，把到根结点的惟一路径，把HHi i 移到适合移到适合它的位置上。在移动的每一步中，将它的位置上。在移动的每一步中，将HiHi的键值与它的父结点的键值与它的父结点HH i i/2/2 的键值相比较，若的键值相比较，若uu若若HiHiHH i i/2/2 ，则则HiHi和和HH i i/2/2 互换（上移），继续互换（上移），继续。uu若若HiHHiH i i/2/2 或或 i i1 1，终止。，终止。第十一张，PPT共四十九页，创作于2

12、022年6月11H5=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=20H1=20，互换。互换后，互换。互换后H2=20H2=20、H1=25H1=25；2 25 52 20 09 91 10

13、 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 120201 117172 29 910104 411115 55 510104 45 53 37 7H1=25H1=25位于根结点。此时位于根结点。此时i=1i=1，程序终止。，程序终止。25251010第十二张，PPT共四十九页，创作于2022年6月12过程 ShiftUp（参见Page 75）输入：数组H1.n和索引i（1in）输出：上移Hi(如果需要)，使它不

14、大于父结点。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(until(i i=1)or done=1)or done 第十三张，PPT共四十九页，创作于2022年6月

15、13ShiftDown 假定对于某个假定对于某个i i n/2n/2（非叶结点）（非叶结点），HHi i 的键值变成小于它的左右子的键值变成小于它的左右子结点结点H2H2i i 或或H2H2i i+1+1 的键值，这样违反了堆的特性，需使用称为的键值，这样违反了堆的特性，需使用称为ShiftDownShiftDown的运算来修复堆。的运算来修复堆。ShiftDown ShiftDown运算使运算使HHi i 下移到二叉树中适合它的位置上。在下移的每一步中，下移到二叉树中适合它的位置上。在下移的每一步中，将将HHi i 的键值与它的子结点键值相比较，若的键值与它的子结点键值相比较，若uuHHi

16、i 子结点键值子结点键值，则则HHi i 与子结点键值中较大者交换（下移），继续；与子结点键值中较大者交换（下移），继续；uuHHi i子结点键值子结点键值 或或 i i n/2n/2，终止。，终止。说明：说明：HHi i 应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个键值较小的子结点的父结点（如果有的话）。键值较小的子结点的父结点（如果有的话）。171710101111111110103 33 3第十四张，PPT共四十九页，创作于2022年6月14说明：若说明：若i i n/2n/2，则该结点位于叶子的位置，无需下移。，则

17、该结点位于叶子的位置，无需下移。n/2n/2 =1515/2/2=7=7 n/2n/2 =1010/2/2=5=5第十五张，PPT共四十九页，创作于2022年6月15H2H2键值由键值由1717变为变为3 32 20 03 39 91 10 01 11 14 45 53 37 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互换。交换后互换

18、。交换后H5=5H5=5，H10=3H10=3；H10=3H10=3位于叶结点位置。位于叶结点位置。i=10i=10 n/2n/2=5=5，程序终止。，程序终止。H2=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 2第十六张，PPT共四十九页，创作于2022年6月16过程过程 ShiftDownShiftDown（Page 76Page 76）输入：数组输入：数组H1.nH

19、1.n和索引和索引i i（11i inn）输出：下移输出：下移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)then6.6.i ii i+1+1 /若有右子结点，选择子结点较大者

20、。若有右子结点，选择子结点较大者。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 第十七张，PPT共四十九页，创作于2022年6月17插入 为了把元素为了把元素x x插入堆插入堆H H中，先将堆的大小增中，先将堆的大小增1 1，然后元素，然后元素x x添加到添加到H H的末尾，再根据需要将的末尾，再根据需要将x x上移，直到满足堆的特性。若上移，直到满足堆的特性。若新堆的个数为新堆的个数为n n，那么堆树的高度为那么堆树的高度为log2n所以将一个元素插入大小为所以将一个元素插入大小为n n的堆中

21、所需要的时间为的堆中所需要的时间为O(log2n)算法4.1 Insert（Page 76-77）输入：堆H1.n和元素x输出：新堆H1.n+1，x为其元素之一。1.nn+12.Hnx3.ShiftUp(H,n)第十八张，PPT共四十九页，创作于2022年6月18删除 要从大小为n的堆中删除元素Hi，可先用Hn替换Hi，然后将堆的大小减1。设原Hi的键值为key(x)，原Hn的键值为key(y)，若key(y)key(x)，则执行上移y。若key(y)key(x)，则执行下移y。若i=1，则表示删除堆的最大值。由于堆树的高度为 log2n，所以删除一个元素所需的时间为O(log2n)。第十九张

22、，PPT共四十九页，创作于2022年6月19算法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 if第二十张，PPT共四十九页，创作于2022年6月204.2.2 创建堆方法一 给出有给出有n n个元素的数组个元素的数组A1.nA1.n，要创建一个包含这些元素的要创建一个包含这些元素的堆可以这样

23、进行：堆可以这样进行：首先假设堆由首先假设堆由1 1个元素构成，然后将第个元素构成，然后将第2 2个、第个、第3 3个元素插入个元素插入堆，直至堆，直至n n个。个。插入第插入第i i个元素，上移次数个元素，上移次数(循环次数循环次数)最多为最多为 loglog2 2i i，因此采用，因此采用这种方法创建堆的时间复杂性为这种方法创建堆的时间复杂性为O(nlogO(nlog2 2n)n)。算法算法 MakeHeapByInsertMakeHeapByInsert（参见（参见Page 77Page 77）输入：输入：n n个元素的数组个元素的数组A1.nA1.n输出：堆输出：堆A1.nA1.n1.

24、1.for for i i2 to n2 to n2.2.ShiftUp(A,ShiftUp(A,i i)3.3.end forend for第二十一张，PPT共四十九页，创作于2022年6月214.15 4.15 给出一个整数数组给出一个整数数组A1.nA1.n，可按照下面的方法建立一个，可按照下面的方法建立一个A A的堆的堆B1.nB1.n。从空堆开始，反复将。从空堆开始，反复将A A中元素插入中元素插入B B，每一次调整，每一次调整当时的堆，直到当时的堆，直到B B包含包含A A中的所有元素。证明在最坏情况下，中的所有元素。证明在最坏情况下，算法运行时间是算法运行时间是(nlogn)(n

25、logn)。解：解：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在最坏情况下在最坏情况下 第二十二张，PPT共四十九页，创作于2022年6月224.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

26、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 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=第二十三张，PPT共四十九页，创作于2022年6月23方法二方法二 设数组设数组A A有有n=10n=10个元素，构造它的几乎完全二叉树

27、个元素，构造它的几乎完全二叉树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的叶子。这样调整可以从内部结点开始，先调整的叶子。这样调整可以从内部结点开始，先调整AA n/2n/2=A=A5 5，随后调整随后调整A A n/2n/2-1-1=A=A4 4 ，直至直至AA1 1。4 41 13 32 28 83 310

28、104 411115 513136 67 77 730308 817179 926261010第二十四张，PPT共四十九页，创作于2022年6月24 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-2=A3=8-2=A3=8AA n/2n/2-3

29、-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 87 710103 31111303026261313

30、171711118 87 710103 34 4第二十五张，PPT共四十九页，创作于2022年6月25算法 MakeHeap(Page 79)输入：n个元素的数组A1.n输出：堆A1.n1.for in/2 downto 12.ShiftDown(A,i)3.end for 设树T的高度为k=log2n，令Aj为对应于树的第i层中的第j个结点，执行ShiftDown(A,j)运算，下移次数(即循环次数)最多为k-i。因为在第i层恰好有2i个结点，故执行总的下移次数的上界为：20(k-0)+21(k-1)+22(k-2)+2k-3(3)+2k-2(2)+2k-1(1)第二十六张，PPT共四十九页

31、，创作于2022年6月26 第第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层结点下移最多次数层结点下移最多次数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层中的第层中

32、的第j j个结点，个结点，执行执行ShiftDown(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)(1)第第2 2层结点下移最多次数层结点下移最多次数2 22 2(k-2)(k-2)第二十七张，PPT共四十九页，创作于2

33、022年6月27可参考本书可参考本书 Page 50Page 50（式（式2.142.14）第二十八张，PPT共四十九页，创作于2022年6月28定理4.1（Page 79）使用算法MakeHeap构造一个n元素的堆，令C(n)为执行该算法的元素比较次数，那么n-1C(n)4n因此构造一个n个元素的堆，算法MakeHeap需要(n)时间和(1)空间。在过程在过程ShiftDownShiftDown的每一次循环中，最多有二次元素比较（有的每一次循环中，最多有二次元素比较（有二个二个if if语句），因此元素总的比较次数上界为语句），因此元素总的比较次数上界为2*2n2*2n。同时过程。同时过程S

34、hiftDownShiftDown至少执行一次循环，所以元素的最少比较次数由内部至少执行一次循环，所以元素的最少比较次数由内部结点数决定，元素总的比较次数下界为结点数决定，元素总的比较次数下界为2 2 n/2n/2 n-1n-1（若原为堆）（若原为堆）。第二十九张，PPT共四十九页，创作于2022年6月294.2.3 堆排序堆排序 给定数组给定数组A1.nA1.n，设每个元素的键值是该元素本身，可采设每个元素的键值是该元素本身，可采用如下方法进行排序：用如下方法进行排序：uu使用算法使用算法MakeHeapMakeHeap将数组将数组A A变换成堆。变换成堆。uu首先将首先将A1A1和和AnA

35、n交换，显然交换，显然AnAn为数组中最大元素，然为数组中最大元素，然后调用过程后调用过程ShiftDownShiftDown将将A1.A1.n-1n-1 转换成堆。转换成堆。uu接着将接着将A1A1和和An-1An-1交换，显然交换，显然An-1An-1为数组中次最大元素，为数组中次最大元素，然后调用过程然后调用过程ShiftDownShiftDown将将A1.A1.n-2n-2 转换成堆。转换成堆。uu交换元素和堆调整过程一直重复，直至堆的大小为交换元素和堆调整过程一直重复，直至堆的大小为1 1。第三十张，PPT共四十九页，创作于2022年6月30算法4.5 HeapSort(Page 8

36、0)输入：n个元素的数组A输出：数组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.14第三十一张，PPT共四十九页，创作于2022年6月31 这个算法在原有空间进行排序，建立堆用(n)时间，ShiftDown运算用O(log2n)时间，并且重复n-1次，显然建立堆所用的时间为低次项，可略。定理4.2(Page 80)算法HeapSort对n个元素排序，需要用O(

37、nlog2n)时间和(1)空间。由此可见，堆排序是最优秀的排序算法。4.2.4 最大堆和最小堆 最大堆：最大键值元素存放在根结点。最小堆：最小键值元素存放在根结点。第三十二张，PPT共四十九页，创作于2022年6月324.3 不相交集数据结构不相交集数据结构（并查集）并查集）是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。如数据结构课中讲到的最小生成树Kruskal算法：Kruskal是一种贪心算法，比较适用于稀疏图:为使生成树上边的权值和最小，则应使生成树中每一条边的权值尽可能地小。具体做法:找出森林中连接任意两棵树的所有边中，具有最小权值的边，如

38、果将它加入生成树中不产生回路，则它就是生成树中的一条边。这里的关键就是如何判断将它加入生成树中不产生回路。第三十三张，PPT共四十九页，创作于2022年6月334.3 不相交集数据结构不相交集数据结构不相交集合及运算不相交集合及运算 设集合设集合S S有有n n个元素，这些元素被分成若干个不相交子集。最初假设每个元素，这些元素被分成若干个不相交子集。最初假设每个元素自成一个集合，这样共有个元素自成一个集合，这样共有n n个子集。经个子集。经n n次合并（次合并（UnionUnion）后，构成）后，构成若干个不相交子集。每个子集用该子集中一个特殊元素命名。若干个不相交子集。每个子集用该子集中一个

39、特殊元素命名。例：假定例：假定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 最初有最初有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个子集依次被命名为个子集依次被命名为1 1、3 3、8 8

40、、9 9。第三十四张，PPT共四十九页，创作于2022年6月34 我们对Union和Find二种不相集运算定义如下：uFind(x)：寻找并返回包含元素x的集合名字。uUnion(x,y)：将包含元素x和y的二个集合用它们的并集替换。并集的名字，或为包含元素x的那个集合的名字，或为包含元素y的那个集合的名字。我们目的是设计这二种运算的有效算法，为此需要一种数据结构，它既要简单，又要能有效实现合并和寻找这二种运算。第三十五张，PPT共四十九页，创作于2022年6月35不相交集数据结构将用于命名子集名称的元素视为根，其余元素视为其后代，每个子集可将用于命名子集名称的元素视为根，其余元素视为其后代，

41、每个子集可用一棵根树来表示，这样便形成了森林。用一棵根树来表示，这样便形成了森林。9 9每个结点都有一个指针。非根结点的指针指向它的父结点；每个结点都有一个指针。非根结点的指针指向它的父结点；根结点的指针值为根结点的指针值为0 0，表示不指向任何结点。，表示不指向任何结点。根结点用作集合的名字。根结点用作集合的名字。森林可方便地用数组森林可方便地用数组A1.nA1.n。AAj j 是是j j的父结点，若的父结点，若AAj j=0=0，说明，说明j j是根结点。是根结点。对于任一元素对于任一元素x x，用用root(x)root(x)表示包含表示包含x x的树的根的树的根，例例root(6)=3

42、root(6)=3。0 03 30 08 82 22 21 10 00 01 11 11 12 23 34 45 56 67 78 89 9101011118 84 41 17 7101011113 32 25 56 6第三十六张，PPT共四十九页，创作于2022年6月36不相交集运算实现Find(x)Find(x)寻找并返回包含元素寻找并返回包含元素x x的树的根。例，的树的根。例，Find(6)=root(6)=3Find(6)=root(6)=3Union(x,y)Union(x,y)将包含将包含x x和和y y的二个不相交集合并成一个集合，也就是说把二的二个不相交集合并成一个集合，也就

43、是说把二棵树合并成一棵树，棵树合并成一棵树，Union(x,y)Union(x,y)可表示为可表示为Union(root(x),root(y)Union(root(x),root(y)。若合并后树的根为若合并后树的根为root(x)root(x)，则有则有Aroot(y)=root(x)Aroot(y)=root(x)。若合并后树的根为若合并后树的根为root(y)root(y)，则有则有Aroot(x)=root(y)Aroot(x)=root(y)。8 84 49 98 84 49 9或或9 98 84 4例，例，Union(4,9)=Union(root(4),root(9)=Union

44、(8,9)Union(4,9)=Union(root(4),root(9)=Union(8,9)8 80 00 01 12 23 34 45 56 67 78 89 9101011118 8第三十七张，PPT共四十九页，创作于2022年6月374.3.1 按秩合并措施按秩合并措施n nn-1n-12 21 1 问题的提出 若直接进行合并运算有个明显缺点，在极端情况下，若直接进行合并运算有个明显缺点，在极端情况下，树有可能退化成线性表。树有可能退化成线性表。假定从单元素集合假定从单元素集合1,2,1,2,nn开始，执行下开始，执行下面的合并序列（假设第二个参数为合并后树的根）：面的合并序列（假设

45、第二个参数为合并后树的根）：Union(1,2),Union(2,3),Union(1,2),Union(2,3),Union(n-1,n)Union(n-1,n)形成的树如左图所示。形成的树如左图所示。执行下面的寻找序列：执行下面的寻找序列：Find(1),Find(2),Find(1),Find(2),Find(n)Find(n)n n次寻找运算总的代价为：次寻找运算总的代价为：第三十八张，PPT共四十九页，创作于2022年6月38引入秩 为了限制每棵树的高度，采用秩合并的措施。给每个结点为了限制每棵树的高度，采用秩合并的措施。给每个结点存储一个非负数作为该结点的秩（记为存储一个非负数作为

46、该结点的秩（记为rankrank），），初始时每个初始时每个结点的秩均为结点的秩均为0 0。设设x x和和y y是二棵不同树的根，执行是二棵不同树的根，执行Union(x,y)Union(x,y)时，比较时，比较rank(x)rank(x)和和rank(y)rank(y)，若若urank(x)rank(y)rank(x)rank(y)rank(x)rank(y)，则使则使x x成为成为y y的父结点，的父结点，rank(x)rank(x)和和rank(y)rank(y)不变。不变。第三十九张，PPT共四十九页，创作于2022年6月39x x1 110100 0y y2 22 21 15 50

47、06 60 0y y1 110100 0 x x2 22 21 15 50 06 60 07 71 110100 0y y2 22 21 15 50 06 60 0 x x2 2rank(x)rank(y)rank(x)rank(y)rank(x)rank(y)，则使则使x x成为成为y y的父结点，的父结点，rank(x)rank(x)和和rank(y)rank(y)不变。不变。y y2 2第四十张，PPT共四十九页，创作于2022年6月40 令x是任意结点，p(x)是x的父结点，有下面二个基本观察结论。观察结论4.1(Page 82)rank(p(x)rank(x)观察结论4.2(Page

48、 82)rank(x)的值初始化为0，在后继合并运算序列中递增，直到x不是根结点。一旦x变成了其它树的子结点，它的秩就不再改变。第四十一张，PPT共四十九页，创作于2022年6月414.3.3 Union-Find算法算法算法算法4.6 Find（参见（参见Page 83)输入：结点输入：结点x输出：输出：root(x)，包含，包含x的树的根。的树的根。0.procedure Find(x)1.yx2.while p(y)0/p(y)=0表示表示y是根结点是根结点3.yp(y)4.end while5.rooty6.return root7.end procedure/注：路径压缩被略去注：路

49、径压缩被略去第四十二张，PPT共四十九页，创作于2022年6月42算法4.7 Union(Page 83)输入：结点x和y输出：包含x和y的二棵树的合并0.procedure Union(x,y)0.procedure Union(x,y)1.1.uFind(x):vFind(y)uFind(x):vFind(y)2.2.if rank(u)rank(v)thenif rank(u)rank(v)then3.3.p(u)p(u)v v /包含包含y y的树的根结点的树的根结点v v是合并后的根结点是合并后的根结点4.4.if rank(u)=rank(v)then if rank(u)=ran

50、k(v)then 5.5.rank(v)=rank(v)+1rank(v)=rank(v)+16.6.end if end if 7.7.else else/rank(u)rank(v)/rank(u)rank(v)8.8.p(v)u p(v)u /包含包含x x的树的根结点的树的根结点u u是合并后的根结点是合并后的根结点9.9.end ifend if10.end procedure10.end procedure第四十三张，PPT共四十九页，创作于2022年6月43设设S=1,2,3,4,5,6,7,8,9S=1,2,3,4,5,6,7,8,9，初始时每棵树由单个元素构成，初始时每棵树由