《算法设计技巧与分析》第4章 堆和不相交集数据结构-教学课件（非AI生成）.ppt

例子246891357UNION(4,8)例子246891357FIND(1)End4.3.4union-find算法的分析引理4.2对于任意的整数:r?0，秩r的节点数至多是n/2r.证明:固定r的一个特定值.当给一个节点x指定秩为r时，对以x为根的树中包含的所有节点都用x标号。由引理4.1可知，标号的节点个数至少是2r.如果树的根节点发生变化，那么新树的根节点的秩至少是r+1，这说明那些用x标号过的节点将不再被标号了。由于标号过的节点个数的最大值是n，而且每个秩为r的根至少有2r个节点，那么至多有n/2r个节点秩为r。4.3.4union-find算法的分析推论4.1任何节点的秩最大是?logn?.证明:如果对于某个节点x，有rank(x)=r??logn?+1，那么由引理4.2可知，至多有n/2?logn?+11个节点的秩为r。.定义4.2时于任意正整数n,Iog*n定义为例如,log*2=1,log*4=2,log*16=3,log*65536=4,log*265536=5.算法分析定理4.3设T(m)表示用按秩合并和路径压缩处理m个合并和寻找运算的交替序列?所需的运行时间，那么在最坏情况下T(m)=O(mlog*n)注意对于几乎所有的实际用途，log*n?5.这说明事实上对于所有的实际应用，运行时间是O(m)。练习4.34.74.114.26算法分析空间:这个算法的一个重大好处在于它是在原有的空间里排序，它不需要辅助存储空间。时间:建立堆用?(n)时间Sift-down运算用O(logj)时间，并且要重复n一1次，Theorem4.2算法HEAPSORT对n个元素排序要用?(nlogn)时间和?(1)空间。4.2.4最小堆和最大堆最大堆:存储在根节点以外的节点的键值，小于或等于存储在它父节点中的键值。最小堆:存储在根节点以外的节点的键值，大于或等于存储在它父节点中的键值。A[1..10]={4,3,8,10,11,13,7,30,17,26}转换成堆.例子171311871034123456789103026Maxheap107111383017261234567891034Minheap4.3不相交集数据结构什么是不相交集?假设给出一个有n个不同元素的集合S，这些元素被分成不相交集合。在每个子集中，用一个特殊的元素作为集合的名字或代表。例如，如果集合S={1,2,…,11}有4个子集，分别是{1,7,10,11},{2,3,5,6},{4,8}和{9},，这些子集可以依次被标记为1,3,8,9。.不相交集的操作FIND(x):寻找并返回包含元素x的集合的名字。UNION(x,y):包含元素x和y的两个集合用它们的并集替换。并集的名字或者是原来包含元素x的那个集合的名字，或者是原来包含元素y的那个集合的名字，这将会在以后确定。例如，如果集合S={1,2,…,11}有4个子集{1,7,10,11},{2,3,5,6},{4,8}和{9},这些子集可以依次被标记为1,3,8,9。FIND(11)运算返回结果1;UNION(1,3)运算返回新子集被标记为1或3我们的目的是什么?我们的目的是设计有效算法进行FIND和UNION操作。为此需要一种数据结构，它既要简单，同时又要考虑到能有效地实现合并和寻找这两种运算。Howtorepresentaset?比特向量表示法S={1,2,…,11}and4subsetsS1={1,7,10,11},S2={2,3,5,6},S3={4,8}andS4={9},S1=10000010011;S2=01101100000;S3=00010001000;S4=00000000100问题:耗费太多额外资源union操作时间与n相关，而不是两个子集的长度List列表表示法Thesubsetisrepresentedasalistofitselements.Forexample,S={1,2,…,11}and4