第四章不相交集数据结构Union-Find分析

1第四章堆和不相交集数据结构4.1引言4.2堆4.3不相交集数据结构24.2堆在许多算法中，需要支持下面两种运算的数据结构：插入元素和寻找最大元素。支持这两种运算的数据结构称为优先队列。普通队列:那么寻找最大元素需要搜索整个队列，开销较大；3排序数组:那么插入运算就需要移动很多元素，开销也较大.优先队列的有效实现是使用一种称为堆的简单数据结构。4定义4.1一个（二叉）堆是一个几乎完全的二叉树，它的每个节点都满足堆的特性：如果v和p(v)分别是节点和它的父节点，那么存储在p(v)中的数据项键值不小于存储在v中数据项的键值。（大顶堆）5堆是满足下列性质的数列{r1,r2,…，rn}：或122iiiirrrr122iiiirrrr数据结构中堆的定义:{12,36,27,65,40,34,98,81,73,55,49}例如:是小顶堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小顶堆)(大顶堆)6rir2ir2i+1若将该数列视作完全二叉树，则r2i是ri的左孩子;r2i+1是ri的右孩子。1236276549817355403498例如:是堆7对数据结构支持下面的运算：Delete-max[H]：删除最大键值的数据项Insert[H,x]：插入项x到堆H中Delete[H,i]：从堆H中删除第i项Makeheap[A]：将数组A转换成堆堆的特性蕴含着：沿着每条从根到叶子的路径，元素的键值以非升序排列。（大顶堆）8有n个节点的堆T（一棵几乎完全的二叉树），可以有一个数组H[1…n]用下面的方式来表示。T的根节点存储在H[1]中。假设T的节点x存储在H[j]中，如果它有左子节点，这个子节点存储在H[2j]中；如果它也有右子节点，这个子节点存储在H[2j+1]中。9元素H[j]的父节点如果不是根节点，则存储在H[j/2]中。104.2.1堆上的运算下面是两个辅助运算Sift-up运算:前提：假定对于某个i1,H[i]变成了键值大于它父节点键值的元素，非堆结构。处理方案：调整破坏堆的数据的位置；实际方法：沿着从H[i]的根节点的唯一一条路经，把H[i]移到适合它的位置上。在沿着路径的每一步上，都将H[i]键值和它父节点的键值H[i/2]相比较。11过程：Sift-up算法输入：数组H[1…n]和位于1和n之间的索引i输出：上移H[i]，以使它不大于父节点1.donefalse2.ifi=1thenexit//节点i是根3.repeat4.ifkey(H[i])key(H[i/2])then互换H[i]和H[i/2]//对比交换5.Elsedonetrue6.ii/27.Untili=1ordone12Sift-down算法：前提：当i≤n/2,设H[2i]和H[2i+1]中最大值为max，如果H[i]中元素的键值变成了小于max，这样就违反了堆的特性，树就不再表示一个堆。调整策略：使H[i]渗到二叉树中适合它的位置上；沿着这条路径的每一步，都将H[i]键值和存储在它子节点中的两个键值里最大的那个相比较。13过程：Sift-down输入：数组H[1…n]和位于1和n之间的索引i输出：下移H[i]，以使它不小于子节点1.donefalse2.if2inthenexit//节点i是叶子，退出3.repeat4.i=2i//待比较位置左子节点5.ifi+1≤nandkey(H[i+1])key(H[i])thenii+1//存在右子节点，且右子节点最大6.ifkey(H[i/2])key(H[i])//与最大节点交换then互换H[i]和H[i/2]7.Elsedonetrue8.Endif9.Until2inordone14算法复杂度分析(1)()(2/3)(1)TnTnSift_down的复杂度分析：（1）以i结点和2i+1,2i+2的调整复杂度所用时间为（2）以2i+1或2i+2结点为父结点来调整的时间最坏是多少？发生调整的几率的树最多是2n/3，（即最底层恰好是半满）。则：，根据递推式求解：O(logn)15算法4.1INSERT输入：堆H[1…n]和元素x输出：新的堆H[1…n+1]，x为其元素之一1.n=n+1{增加H的大小}2.H[n]x3.SIFT-UP(H,n)16插入（1）先将堆大小加1，然后将x添加到H的末尾，再根据需要，把x上移，直到满足堆特性，（2）观察结论3.4可知，如果n是新堆的大小，那么堆树的高度是logn，所以将一个元素插入大小为n的堆中所需要的时间是O(logn)。17算法4.2DELETE//删除某个元素输入：非空堆H[1…n]和位于1和n之间的索引i输出：删除H[i]后的新堆H[1…n-1]1.xH[i];yH[n]//删除x，最后一个数据暂存y2.n=n-1//数组大小减13.Ifi=n+1thenexit//删除的元素正好是最后一个，不需要任何操作4.H[i]y;//不是最后一个则取回最后一个，先放入H[i]中5.Ifkey(y)≥key(x)thenSIFT-UP(H,i)6.ElseSIFT-DOWN(H,i)//根据需要进行调整7.ENDIF18删除复杂度：这些在算法DELETE中描述。有观察结论3.4可知，堆树的高度是logn，所以从一个大小为n的堆中删除一个元素所需要的时间是O(logn)。19算法4.3DELETEMAX//删除根节点输入：堆H[1…n]输出：返回最大值元素x并将其从堆中删除1.xH[1]2.DELETE(H,1)3.Returnx20删除最大值复杂度分析：（1）在堆中返回最大键值元素需要Θ(1)的时间，因为这个元素是树的根节点。(2)修复堆需要一定的时间。显然，这项运算的时间复杂性就是删除运算的时间复杂性，即O(logn)。214.2.2创建堆给出一个A[1…n]，创建一个包含这些元素的堆是容易的：从空的堆开始，不断插入一个元素，直到A完全被转移到堆中为止。因为插入第j个键值用时O(logj)，因此用此方法创建堆栈的时间复杂性是O(nlogn)。22看另外一个堆建立方法：在Θ(n)的时间内，用n个元素来建立一个堆，下面给出这种方法的实现细节。23(1)将堆H[1…n]的树的节点以自顶向下、从左到右的方式从1到n编码。(2)把一棵n个节点的几乎完全的二叉树转换成堆H[1…n]。(3)从最后一个节点开始（编码为n的那个）到根节点（编码为1的节点），逐个扫描所有的节点，根据需要，每一次将以当前节点为根节点的子树转换成堆。见例4.3创建堆的例子(手写)24算法MAKEHEAP构建了一个堆，其数据项是存储在数组A[1…n]中的元素。算法4.4MAKEHEAP输入：n个元素的数组A[1…n]输出：A[1…n]转换成堆1.Forin/2downto12.SIFT-DOWN(A,i)3.Endfor//注：叶子节点不需要处理，所以必须从n/2开始处理，A[n/2+1]，A[n/2+2],..A[n]对应于数的叶子节点25算法复杂度分析：(1)设T是一个完全二叉树，高度是k=logn。(2)设A[j]对应第i层的第j个结点，则调用sift-down函数需要调用的次数应该最多是k-i(注：k是树的高度)（自底而上扫描连接的数据）。(3)根据二叉树的理论知：二叉树的第i层最多有2i个结点，则循环的上界应该为：10111()22()2(1)...2(1)2kikikikkn26定理4.1算法MAKEHEAP用来构造一个n个元素的堆，令C(n)为执行该算法的元素比较次数，那么n-1≤C(n)＜4n。因此，算法需要Θ(n)时间和Θ(1)空间构造一个n元素的堆。观察sift-down函数，每一次循环过程，包含有两个if语句，故最多两次元素比较，故元素比较的总次数上界是2*2n=4n；观察下界：调用sift-down函数至少要执行一次循环，所以元素的最小比较次数应为:2*n/2=n-1。27另外一种分析方法：1、简单的分析：每次调用SIFT-DOWN()函数的时间为O(logn)，一共应该有n/2次调用，所以总的时间复杂度上线是O(nlogn)。但是这个上限太高了。（这就意味着几乎每一个结点都在执行sift_down()函数行为）28分析一个确界：1、事实上，需要执行SIFT-DOWN()函数的结点很少，而且对于不同的节点执行SIFT-DOWN()函数的次数也是不同的，这跟每一个结点所处的高度和所连接的数据相关。29logn1/2hnloglog1100()()22nnhhhhnnOhOn一个n元素的堆的高度是，在任意的高度h上，最多有结点数设SIFT-DOWN()在h层上的作用时间是O(h)，则应该有一个上确界：（1）3020(1)kkxkxx2012212(1)2khhlog10()(2)()2nhhnOnOnOn数论上存在如下等式成立：设x=1/2带入（1）的右边的和式314.2.3堆排序算法SELECTIONSORT(选择排序)的复杂度：用线性搜索来找最小值的时间需要用Θ(n)的时间，算法就要用Θ(n2)时间。如何提高选择排序的复杂度呢，使用堆是一个好的选择。32给出数组A[1…n]，将其中的元素用如下方法以非降序有效排序。step1.首先将A变换成堆，并使其具有这样的性质，每个元素的键值是该元素本身，即key(A[i])=A[i],1≤i≤n。33step2.由于A中各项的最大值存储在A[1]中，可以将A[1]和A[n]交换，使得A[n]是数组中最大元素。(排序：将数据依大小，顺序放在数组中，最后一个是最大的，故交换A[1]和A[n])34这时，A[1]中的元素可能小于存放在它的一个子节点中的元素，于是用过程SIFT-DOWN将A[1…n-1]转换成堆。(调整堆)接下来将A[1]和A[n-1]交换，并调整数组A[1…n-2]成为堆。交换元素和调整堆的过程一直重复，直到堆的大小变成1为止，这时A[1]是最小的。35算法4.5HEAPSORT输入：n个元素的数组A[1…n]输出：以非降序排列的数组A1.MAKEHEAP(A)2.forjndownto2//j从n依次递减3.互换A[1]A[j]4.SIFT-DOWN(A[1…j-1],1)5.endfor定理4.2算法HEAPSORT对n个元素排序要用O(nlogn)时间和Θ(1)的空间。364.2.4最小堆和最大堆到现在为止，我们把堆看作是一个数据结构，它的主要运算是检索有最大键值得元素。一般来说，可以容易得把堆修改成使得有最小键值得元素存储在根节点中。在这种情况下，堆的特性要求存储在根节点以外的节点的键值，大于或等于存储在它父节点中的键值。这两种类型的堆一般可以看作是最大堆和最小堆。37优先级队列的应用1、堆作为一个优先级队列，用于排序吗？可以！但是，应用最多的还是：快速排序。2、基于最大堆的最大优先级队列。优先级队列：一种用于维护由一组元素构成的集合S的数据结构。支持如下操作：38INSERT(S，x):MAXIMUM(S)：EXTRACT_MAX(S):去掉并返回S中的具有最大关键字的元素。INCREASE_KEY(S,x,k):将元素x的关键字的值增加到k，这里的k值不能小于x的原关键字的值393、应用举例：分时OS的作业调度。应用最大堆的优先级队列，记录需要被调度的各种作业以及他们之间的优先级的关系。作业完成或被中断时，应用EXTRACT_MAX(S)从所有的等待队列里面选择一个优先级最大的作业进入调度，任何时候一个新作业都可以使用INSERT()操作加入到队列中。404、小顶堆基于事件驱动的模拟器（1）队列中的各项是需要模拟的事件；（2）每一个事件都需要一个发生事件作为关键字；（3）事件模拟需要按照事件发生的时