第4章 堆和不相交数据结构

1第4章堆和不相交集数据结构上海第二工业大学温敬和[e-mail]2008年4月4日24.1引言（堆、不相交集）4.2堆4.2.1堆上的运算4.2.2创建堆4.2.3堆排序4.2.4最大堆和最小堆4.3不相交集数据结构4.3.1按秩合并措施4.3.3Union-Find算法4.3.2路径压缩4.3.4Union-Find算法的分析（略）34.2堆㈠堆的引入在许多算法中，需要支持下面二种运算：插入元素寻找最大值元素（或最小值元素）支持这二种运算的数据结构称为优先队列。可采用下述三种方法实现优先队列：①使用普通队列（或数组），插入容易（尾部），但寻找最大值需搜索整个队列，开销比较大。②使用排序数组，寻找最大值元素容易，插入操作需移动很多元素。③使用堆，寻找最大值元素容易，插入操作仅需移动少量元素。4定义4.1（Page74）一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设v是一个结点，p(v)是v的父结点，那么存储在p(v)中的数据项键值大于或等于存储在v中的数据项键值。㈡堆的定义（二叉堆）几乎完全二叉树（Page71）如果一棵二叉树，（在底层）除了最右边位置上的一个或几个叶子可能缺少外，它是丰满的，我们定义它为几乎完全二叉树。①②③④⑤⑥⑦⑧⑨⑩5堆数据结构支持下列运算DeleteMax[H]：从一个非空堆H中，删除最大键值的数据项，并返回该数据；Insert[H,x]：将数据项x插入堆H中；Delete[H,i]：从堆中删除第i项；MakeHeap[A]：将数组转换为堆。堆的蕴含特性：沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。6㈢堆的表示有n个结点堆T，可以用一个数组H[1..n]用下面方式来表示：T的根结点存储在H[1]中；设T的结点存储在H[j]中，如果它有左子结点，则这个左子结点存储在H[2j]中；如果它还有右子结点，这个右子结点存储在H[2j+1]；若元素H[j]不是根结点，它的父结点存储在H[j/2]中。由“几乎完全二叉树”的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。堆具有如下性质：key(H[j/2])≥key(H[j])2≤j≤n72011729310411546573879510㈣堆和它的数组表示法把存储在堆中的数据项视为键值。按树的结点“自顶向下”、“从左至右”、“按1到n”的顺序进行编号，那么数组元素H[i]对应树中编号为i的结点。2017910114537512345678910H[2]=17的左子结点为H[2*2]=H[4]=10H[2]=17的右子结点为H[2*2+1]=H[5]=11H[9]=7的父结点为H[9/2]=H[4]=10沿着每条从根到叶子的路径,元素的键值以降序排列。84.2.1堆上的运算㈠ShiftUp假定对于某个i＞1，H[i]的键值变成大于它父结点的键值，这样违反了堆的特性，需使用称为ShiftUp的运算来修复堆。ShiftUp运算沿着从H[i]到根结点的惟一路径，把H[i]移到适合它的位置上。在移动的每一步中，将H[i]的键值与它的父结点H[i/2]的键值相比较，若若H[i]H[i/2]，则H[i]和H[i/2]互换（上移），继续。若H[i]≤H[i/2]或i=1，终止。9②H[5]=25和H[2]=17互换，H[5]=17,H[2]=25。①H[10]=25和H[5]=11互换，H[10]=11,H[5]=25。2011729101154537510→25例，H[10]的键值由5变为25。20179101145372512345678910③H[2]=25和H[1]=20互换，H[2]=20,H[1]=25。25209101745371120179102545371120259101745371110过程ShiftUp（参见Page75）输入：数组H[1..n]和索引i（1≤i≤n）输出：上移H[i](如果需要)，使它不大于父结点。0.procedureShiftUp(H[1..n],i)1.done←false2.ifi=1thenexit//根结点3.repeat4.ifkey(H[i])key(H[i/2])then5.互换H[i]和H[i/2]6.else7.done←true8.endif9.i←i/210.untili=1ordone11.endprocedure11㈡ShiftDown假定对于某个i≤n/2，H[i]的键值变成小于它的左右子结点H[2i]或H[2i+1]的键值，这样违反了堆的特性，需使用称为ShiftDown的运算来修复堆。ShiftDown运算使H[i]下移到二叉树中适合它的位置上。在下移的每一步中，将H[i]的键值与它的子结点键值相比较，若H[i]子结点键值，则H[i]与子结点键值中较大者交换（下移），继续；H[i]≥子结点键值或i＞n/2，终止。说明1：H[i]应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个键值较小的子结点的父结点（如果有的话）。17→310111110312⑵说明：若i＞n/2，则该结点位于叶子的位置，无需下移。①②③④⑤⑥⑦⑧⑨⑩①②③④⑤⑥⑦⑧⑨⑩○○○○○n/2=15/2=7n/2=10/2=513201172→39101154537510①H[2]=3和H[5]=11互换，H[2]=11,H[5]=3。例，H[2]的键值由17变为3。203910114537512345678910②H[5]=3和H[10]=5互换，H[5]=5,H[10]=3。2011910545373201191034537514过程ShiftDown（Page76）输入：数组H[1..n]和索引i（1≤i≤n）输出：下移H[i](如果需要)，使它不小于子结点。0.procedureShiftDown(H[1..n],i)1.done←false2.if2inthenexit//H[i]是叶结点，无需下移。3.repeat4.i←2i//i指向子结点5.if(i+1≤n)and(key(H[i+1])key(H[i]))then6.i←i+1//若有右子结点，选择子结点较大者。7.endif8.ifkey(H[i/2])key(H[i])then9.互换H[i]和H[i/2]10.else11.done←true12.endif13.until2inordone14.endprocedure15㈢插入为了把元素x插入堆H中，先将堆的大小增1，然后元素x添加到H的末尾，再根据需要将x上移，直到满足堆的特性。若新堆的个数为n，那么堆树的高度为log2n所以将一个元素插入大小为n的堆中所需要的时间为O(log2n)算法4.1Insert（Page76-77）输入：堆H[1..n]和元素x输出：新堆H[1..n+1]，x为其元素之一。1.n←n+12.H[n]←x3.ShiftUp(H,n)16㈣删除要从大小为n的堆中删除元素H[i]，可先用H[n]替换H[i]，然后将堆的大小减1。设原H[i]的键值为key(x)，原H[n]的键值为key(y)，若key(y)≥key(x)，则执行上移y。若key(y)＜key(x)，则执行下移y。若i=1，则表示删除堆的最大值。由于堆树的高度为log2n，所以删除一个元素所需的时间为O(log2n)。17算法4.2Delete（Page77）输入：非空堆H[1..n]和索引i（1≤i≤n）输出：删除H[i]的新堆H[1..n-1]1.x←H[i]:y←H[n]//H[i]为要删除的元素2.n←n-13.ifi=n+1thenexit//删除堆最后一个元素4.H[i]←y5.ifkey(y)≥key(x)then6.ShiftUp(H,i)7.else8.ShiftDown(H,i)9.endif18㈤创建堆①方法一给出有n个元素的数组A[1..n]，要创建一个包含这些元素的堆可以这样进行：首先假设堆由1个元素构成，然后将第2个、第3个元素插入堆，直至n个。插入第i个元素,上移次数（循环次数）最多为log2i，因此采用这种方法创建堆的时间复杂性为O(nlog2n)。算法MakeHeapByInsert（参见Page77）输入：n个元素的数组A[1..n]输出：堆A[1..n]1.fori=2ton2.ShiftUp(A,i)3.endfor19②方法二设数组A有n=10个元素，构造它的几乎完全二叉树T。如下所示：413283104115136773081792610438101113730172612345678910显然T不是堆。观察数组A的下列元素：A[n/2+1]=A[6]=13，…，A[n]=A[10]=26。它们对应于T的叶子。这样调整可以从内部结点开始，先调整A[n/2]=A[5]=11，随后调整A[n/2-1]=A[4]=10，…，直至A[1]=4。20413283104115136773081792610438101113730172612345678910A[n/2]=A[5]=11A[n/2-1]=A[4]=10A[n/2-2]=A[3]=8A[n/2-3]=A[2]=3A[n/2-4]=A[1]=443810261373017114383026137101711431330268710171143013326871017114301317268710311304131726871031130261317487103113026131711871034几乎完全二叉树的变化详见黑板21算法MakeHeap(Page79)输入：n个元素的数组A[1..n]输出：堆A[1..n]1.fori=n/2downto12.ShiftDown(A,i)3.endfor设树T的高度为k=log2n，令A[j]为对应于树的第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)22○○○○○○○第0层结点下移最多次数20(k-0)令k=log2n，设n=31则k=4。○○○○○第1层结点下移最多次数21(k-1)第i层结点下移最多次数2i(k-i)第k-1层结点下移最多次数2i(k-(k-1))=2i(1)第k层结点下移最多次数2i(k-k))=2k(0)设树T的高度为k=log2n，令A[j]为对应于树的第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)23nknniiikkkkkkkkiikkiikkiikkkkkk2)222()164834221(2/2222)2()2)(1()2)(2()2(2)2(1)1(2)2(2)3(2)2(2)1(2211101221123210可参考本书Page50（式2.14）kkiiki2222124定理4.1（Page79）使用算法MakeHeap构造一个n元素的堆，令C(n)为执行该算法的元素比较次数，那么n-1≤C(n)≤4n因此构造一个n元素的堆，算法MakeHeap需要Θ(n)时间和Θ(1)空间。在过程ShiftDown的每一次循环中，最多有二次元素比较（有二个if语句），因此元素总的比较次数上界为4n（2*2n）。同时，过程ShiftDown至少执行一次循环，所以元素的最少