堆与不相交数据结构

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

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：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in) ，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2 (2) 如果2in，则结点i无左孩子；如果2in ，则其左孩子是2i (3) 如果2i+1n，则结点i无右孩子；如果2i+1n ，则其右孩子是2i+1

3、第四张，PPT共四十九页，创作于2022年6月44.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算法的分析（略）第五张，PPT共四十九页，创作于2022年6月54.2 堆堆的引入在许多算法中，需要支持下面二种运算：插入元素寻找最大值元素（或最小值元素）支持这二种运算的数据结构称为优先队列。可采用下述三种方法实现优先队列：使用普通队列（或数组），插入容易（尾部），但寻找最

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

5、22年6月7堆数据结构支持下列运算DeleteMax(H)：从一个非空堆H中，删除最大键值的数据项，并返回该数据；Insert(H,x)：将数据项x插入堆H中；Delete(H,i)：从堆中删除第i项；MakeHeap(A)：将数组转换为堆。 堆的蕴含特性： 沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。第八张，PPT共四十九页，创作于2022年6月8堆的表示 有n个结点堆T，可以用一个数组H1.n用下面方式来表示：T的根结点存储在H1中；设T的结点存储在Hj中，如果它有左子结点，则这个左子结点存储在H2j中。如果它还有右子结点，这个右子结点存储在H2j+1；若元素Hj不是根结

6、点，它的父结点存储在Hj/2中。 由 “几乎完全二叉树” 的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。 堆具有如下性质： key(Hj/2)key(Hj) 2jn第九张，PPT共四十九页，创作于2022年6月92011729310411546573879510堆和它的数组表示法 把存储在堆中的数据项视为键值。按树的结点“自顶向下”、“从左至右”、“按1到n”的顺序进行编号，那么数组元素Hi对应树中编号为i的结点。 2017910114537512345678910H2=17的左子结点为H2*2=H4=10H2=17的右子结点为H2*2+1=H5=11H9=7的父结点为H 9/2

7、 =H4=10 沿着每条从根到叶子的路径，元素的键值以降序排列。第十张，PPT共四十九页，创作于2022年6月104.2.1 堆上的运算ShiftUp 假定对于某个i1，Hi的键值变成大于它父结点的键值，这样违反了堆的特性，需使用称为ShiftUp的运算来修复堆。 ShiftUp运算沿着从Hi到根结点的惟一路径，把Hi移到适合它的位置上。在移动的每一步中，将Hi的键值与它的父结点Hi/2的键值相比较，若若HiHi/2，则Hi和Hi/2互换（上移），继续。若HiHi/2 或 i1，终止。 第十一张，PPT共四十九页，创作于2022年6月11H5=25H2=17，互换。互换后H5=17、H2=25

8、；H10=25H5=11，互换。互换后H10=11、H5=25；H10的键值由5变为2520179101145372512345678910H2=25H1=20，互换。互换后H2=20、H1=25；25209101745371120179102545371120259101745371120117291041155104537H1=25位于根结点。此时i=1，程序终止。2510第十二张，PPT共四十九页，创作于2022年6月12过程 ShiftUp（参见Page 75）输入：数组H1.n和索引i（1in）输出：上移Hi(如果需要)，使它不大于父结点。1.donefalse2.if i1 the

9、n exit/根结点3.repeat4. if key(Hi)key(Hi/2) then 5.互换Hi和Hi/26. else 7.donetrue8. end if9. i i/210.until (i=1) or done 第十三张，PPT共四十九页，创作于2022年6月13ShiftDown 假定对于某个i n/2（非叶结点），Hi的键值变成小于它的左右子结点H2i或H2i+1 的键值，这样违反了堆的特性，需使用称为ShiftDown的运算来修复堆。 ShiftDown运算使Hi下移到二叉树中适合它的位置上。在下移的每一步中，将Hi的键值与它的子结点键值相比较，若Hi子结点键值，则Hi

10、与子结点键值中较大者交换（下移），继续；Hi子结点键值 或 in/2，终止。说明：Hi应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个键值较小的子结点的父结点（如果有的话）。171011111033第十四张，PPT共四十九页，创作于2022年6月14说明：若in/2，则该结点位于叶子的位置，无需下移。 n/2 = 15/2=7n/2 = 10/2= 5第十五张，PPT共四十九页，创作于2022年6月15H2键值由17变为320391011453751234567891020119105453732011910345375H5=3小于H10=5，所以H5和H10互换。交换后H5=5，H

11、10=3；H10=3位于叶结点位置。 i=10n/2=5，程序终止。H2=3小于H4和H5，因为H4H5，所以H2和H5互换。交换后H2=11，H5=3；201172931041154537532第十六张，PPT共四十九页，创作于2022年6月16过程 ShiftDown（Page 76）输入：数组H1.n和索引i（1in）输出：下移Hi（如果需要），使它不小于子结点。1.donefalse2.if 2in then exit/Hi是叶结点，无需下移。3.repeat4. i2i /i指向子结点5. if (i+1n) and (key(Hi+1)key(Hi) then6. ii+1 /若有

12、右子结点，选择子结点较大者。7. end if8. if key(Hi/2)n) or done 第十七张，PPT共四十九页，创作于2022年6月17插入 为了把元素x插入堆H中，先将堆的大小增1，然后元素x添加到H的末尾，再根据需要将x上移，直到满足堆的特性。若新堆的个数为n，那么堆树的高度为log2n所以将一个元素插入大小为n的堆中所需要的时间为O(log2n)算法4.1 Insert（77）输入：堆H1.n和元素x输出：新堆H1.n+1，x为其元素之一。1.nn+12.Hnx3.ShiftUp(H,n)第十八张，PPT共四十九页，创作于2022年6月18删除 要从大小为n的堆中删除元素H

13、i，可先用Hn替换Hi，然后将堆的大小减1。设原Hi的键值为key(x)，原Hn的键值为key(y)，若key(y)key(x)，则执行上移y。若key(y)key(x)，则执行下移y。若i=1，则表示删除堆的最大值。 由于堆树的高度为 log2n，所以删除一个元素所需的时间为O(log2n)。第十九张，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

14、(y)key(x) then6.ShiftUp(H,i)7.else8.ShiftDown(H,i)9.end if第二十张，PPT共四十九页，创作于2022年6月204.2.2 创建堆方法一 给出有n个元素的数组A1.n，要创建一个包含这些元素的堆可以这样进行： 首先假设堆由1个元素构成，然后将第2个、第3个元素插入堆，直至n个。 插入第i个元素，上移次数(循环次数)最多为log2i，因此采用这种方法创建堆的时间复杂性为O(nlog2n)。算法 MakeHeapByInsert（参见Page 77）输入：n个元素的数组A1.n输出：堆A1.n1.for i2 to n2.ShiftUp(A,

15、i)3.end for第二十一张，PPT共四十九页，创作于2022年6月214.15 给出一个整数数组A1.n，可按照下面的方法建立一个A的堆B1.n。从空堆开始，反复将A中元素插入B，每一次调整当时的堆，直到B包含A中的所有元素。证明在最坏情况下，算法运行时间是(nlogn)。解：1.for i1 to n2.BiAi3.ShiftUp(B,i) /ShiftUp(B1.i,i)4.end for在最坏情况下第二十二张，PPT共四十九页，创作于2022年6月224.16 用图说明练习4.15的算法对于下面数组的运算。解：A1.8 69271843B1.1=669969629627972697

16、261972618978612978612497861243B1.8=B1.2=B1.3=B1.4=B1.5=B1.7=B1.6=第二十三张，PPT共四十九页，创作于2022年6月23方法二 设数组A有n=10个元素，构造它的几乎完全二叉树T，如下所示，显然T不是堆。438101113730172612345678910 观察数组A的元素：An/2+1=A6，An=A10，它们对应于T的叶子。这样调整可以从内部结点开始，先调整An/2=A5， 随后调整An/2-1=A4 ， ，直至A1。413283104115136773081792610第二十四张，PPT共四十九页，创作于2022年6月24

17、 41 32 83 104 115136 77308 179 2610438101113730172612345678910An/2=A5=11An/2-1=A4=10An/2-2=A3=8An/2-3=A2=3 An/2-4=A1=443810261373017114383026137101711431330268710171143013326871017114301317268710311304131726871031130261317487103113026131711871034第二十五张，PPT共四十九页，创作于2022年6月25算法 MakeHeap (Page 79)输入：n个元

18、素的数组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共四十九页，创作于2022年6月26第0层结点下移最多次数20(k-0)令k=log2n，设n=31则k=4。第1层结点下移最多次数21(k-1)第i层结

19、点下移最多次数2i(k-i)第k-1层结点下移最多次数2k-1(k-(k-1)=2k-1(1) 设树T的高度为klog2n，令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) 第2层结点下移最多次数22(k-2)第二十七张，PPT共四十九页，创作于2022年6月27可参考本书 Page 50（式2.14）第二十八张，PPT共四十九页，创作于2022年6月28定理4.1（Pa

20、ge 79） 使用算法MakeHeap构造一个n元素的堆，令C(n)为执行该算法的元素比较次数，那么n-1C(n)4n因此构造一个n个元素的堆，算法MakeHeap需要(n)时间和(1)空间。 在过程ShiftDown的每一次循环中，最多有二次元素比较（有二个if语句），因此元素总的比较次数上界为2*2n。同时过程ShiftDown至少执行一次循环，所以元素的最少比较次数由内部结点数决定，元素总的比较次数下界为2n/2n-1（若原为堆）。第二十九张，PPT共四十九页，创作于2022年6月294.2.3 堆排序 给定数组A1.n，设每个元素的键值是该元素本身，可采用如下方法进行排序：使用算法Ma

21、keHeap将数组A变换成堆。首先将A1和An交换，显然An为数组中最大元素，然后调用过程ShiftDown将A1.n-1转换成堆。接着将A1和An-1交换，显然An-1为数组中次最大元素，然后调用过程ShiftDown将A1.n-2转换成堆。交换元素和堆调整过程一直重复，直至堆的大小为1。第三十张，PPT共四十九页，创作于2022年6月30算法4.5 HeapSort(Page 80)输入：n个元素的数组A输出：数组A中元素按升序排列1.MakeHeap(A)2.for jn downto 23.互换A1和Aj4.ShiftDown(A1.j-1,1)5.end for 这个算法在原有空间进

22、行排序，建立堆用(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(nlog2n)时间和(1)空间。由此可见，堆排序是最优秀的排序算法。4.2.4 最大堆和最小堆 最大堆：最大键值元素存放在根结点。 最小堆：最小键值元素存放在根结点。第三十二张，PPT共四十九页，创作于202

23、2年6月324.3 不相交集数据结构（并查集）是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。如数据结构课中讲到的最小生成树Kruskal算法：Kruskal是一种贪心算法，比较适用于稀疏图:为使生成树上边的权值和最小，则应使生成树中每一条边的权值尽可能地小。具体做法:找出森林中连接任意两棵树的所有边中，具有最小权值的边，如果将它加入生成树中不产生回路，则它就是生成树中的一条边。这里的关键就是如何判断将它加入生成树中不产生回路。第三十三张，PPT共四十九页，创作于2022年6月334.3 不相交集数据结构不相交集合及运算 设集合S有n个元素，这些元素

24、被分成若干个不相交子集。最初假设每个元素自成一个集合，这样共有n个子集。经n次合并（Union）后，构成若干个不相交子集。每个子集用该子集中一个特殊元素命名。 例：假定n个元素的集合S=1,2,3,4,5,6,7,8,9,10,11 最初有11个子集1,2,3,4,5,6,7,8,9,10,11 每个子集的名称分别为子集中元素本身。 经若干次合并后，形成4个子集，假设它们是1,7,10,11,2,3,5,6,4,8,9 4个子集依次被命名为1、3、8、9。第三十四张，PPT共四十九页，创作于2022年6月34 我们对Union和Find二种不相集运算定义如下：Find(x)：寻找并返回包含元素

25、x的集合名字。Union(x,y)：将包含元素x和y的二个集合用它们的并集替换。并集的名字，或为包含元素x的那个集合的名字，或为包含元素y的那个集合的名字。 我们目的是设计这二种运算的有效算法，为此需要一种数据结构，它既要简单，又要能有效实现合并和寻找这二种运算。第三十五张，PPT共四十九页，创作于2022年6月35不相交集数据结构将用于命名子集名称的元素视为根，其余元素视为其后代，每个子集可用一棵根树来表示，这样便形成了森林。9每个结点都有一个指针。非根结点的指针指向它的父结点；根结点的指针值为0，表示不指向任何结点。根结点用作集合的名字。森林可方便地用数组A1.n。Aj是j的父结点，若Aj

26、=0，说明j是根结点。对于任一元素x，用root(x)表示包含x的树的根，例root(6)=3。030822100111234567891011841710113256第三十六张，PPT共四十九页，创作于2022年6月36不相交集运算实现Find(x) 寻找并返回包含元素x的树的根。例，Find(6)=root(6)=3Union(x,y) 将包含x和y的二个不相交集合并成一个集合，也就是说把二棵树合并成一棵树，Union(x,y)可表示为Union(root(x),root(y)。 若合并后树的根为root(x)，则有Aroot(y)=root(x)。 若合并后树的根为root(y)，则有A

27、root(x)=root(y)。849849或984例，Union(4,9)=Union(root(4),root(9)=Union(8,9)80012345678910118第三十七张，PPT共四十九页，创作于2022年6月374.3.1 按秩合并措施nn-121 问题的提出 若直接进行合并运算有个明显缺点，在极端情况下，树有可能退化成线性表。 假定从单元素集合1,2, ,n开始，执行下面的合并序列（假设第二个参数为合并后树的根）： Union(1,2),Union(2,3), ,Union(n-1,n)形成的树如左图所示。 执行下面的寻找序列：Find(1),Find(2), ,Find(

28、n)n次寻找运算总的代价为：第三十八张，PPT共四十九页，创作于2022年6月38引入秩 为了限制每棵树的高度，采用秩合并的措施。给每个结点存储一个非负数作为该结点的秩（记为rank），初始时每个结点的秩均为0。 设x和y是二棵不同树的根，执行Union(x,y)时，比较rank(x)和rank(y)，若rank(x)rank(y)，则使x成为y的父结点， rank(x)和rank(y)不变。第三十九张，PPT共四十九页，创作于2022年6月39x1100y2215060y1100 x221506071100y2215060 x2rank(x)rank(y)，则使x成为y的父结点， rank(

29、x)和rank(y)不变。y2第四十张，PPT共四十九页，创作于2022年6月40 令x是任意结点，p(x)是x的父结点，有下面二个基本观察结论。观察结论4.1(Page 82) rank(p(x)rank(x)观察结论4.2(Page 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.

30、while p(y)0/p(y)=0表示y是根结点3.yp(y)4.end while5.rooty6.return root7. end procedure/注：路径压缩被略去第四十二张，PPT共四十九页，创作于2022年6月42算法4.7 Union(Page 83)输入：结点x和y输出：包含x和y的二棵树的合并0. procedure Union(x,y)1.uFind(x) : vFind(y)2.if rank(u)rank(v) then3.p(u)v /包含y的树的根结点v是合并后的根结点4.if rank(u)=rank(v) then 5.rank(v)=rank(v)+16.end if 7.else /rank(u)rank(v)8.p(v)u /包含x的树的根结点u是合并后的根结点9.end if10. end procedure第四十三张，PPT共四十九页，创作于2022年6