左偏树的特点及其应用 下载本文

内容发布更新时间 : 2024/12/23 18:12:42星期一 下面是文章的全部内容请认真阅读。

IOI2005国家集训队论文 黄源河

此时删除操作也可以结束了。如果p是右子树,这时有两种可能:一种是p的距离仍小于等于q的左子树距离,这时我们直接调整q的距离就行了;另一种是p的距离大于q的左子树距离,这时我们需要交换q的左右子树并调整q的距离,交换完了以后q的右子树是原来的左子树,它的距离加1只能等于或大于q的原有距离,如果等于成立,删除操作可以结束了,否则q的距离将增大,我们还要对q的父节点做出相同的处理。

删除任意已知节点操作的代码如下:

Procedure Delete(x) q ← parent(x) p ← Merge(left(x), right(x)) parent(p) ← q If q ≠ NULL and left(q) = x Then left(q) ← p If q ≠ NULL and right(q) = x Then right(q) ← p While q ≠ NULL Do If dist(left(q)) < dist(right(q)) Then swap(left(q), right(q)) If dist(right(q))+1 = dist(q) Then Exit Procedure dist(q) ← dist(right(q))+1 p ← q q ← parent(q) End While End Procedure

下面分两种情况讨论删除操作的时间复杂度。

情况1:p的距离减小了。在这种情况下,由于q的距离只能缩小,当循环结束时,要么根节点处理完了,q为空;要么p是q的右子树并且dist(p)+1=dist(q);如果dist(p)+1>dist(q),那么p一定是q的左子树,否则会出现q的右子树距离缩小了,但是加1以后却大于q的距离的情况,不符合左偏树的性质3。不论哪种情况,删除操作都可以结束了。注意到,每一次循环,p的距离都会加1,而在循环体内,dist(p)+1最终将成为某个节点的距离。根据性质4,任何的距离都不会超过logn,所以循环体的执行次数不会超过logn。

情况2:p的距离增大了。在这种情况下,我们将必然一直从右子树向上调整,直至q为空或p是q的左子树时停止。一直从右子树升上来这个事实说明了循环的次数不会超过logn(性质4)。

最后我们看到这样一个事实,就是这两种情况只会发生其中一个。如果某种情况的调整结束后,我们已经知道要么q为空,要么dist(p)+1 = dist(q),要么p

第 11 页 共 21 页

IOI2005国家集训队论文 黄源河

是q的左子树。这三种情况都不会导致另一情况发生。直观上来讲,如果合并后的新子树导致了父节点的一系列距离调整的话,要么就一直是往小调整,要么是一直往大调整,不会出现交替的情况。

我们已经知道合并出新子树p的复杂度是O(logn),向上调整距离的复杂度也是O(logn),故删除操作的最坏情况的时间复杂度是O(logn)。如果左偏树非常倾斜,实际应用情况下要比这个快得多。

3.6 小结

本章介绍了左偏树的各种操作,我们可以看到,左偏树作为可并堆的实现,它的各种操作性能都十分优秀,且编程复杂度比较低,可以说是一个“性价比”十分高的数据结构。左偏树之所以是很好的可并堆实现,是因为它能够捕捉到具有堆性质的二叉树里面的一些其它有用信息,没有将这些信息浪费掉。根据堆性质,我们知道,从根节点向下到任何一个外节点的路径都是有序的。存在越长的路径,说明树的整体有序性越强,与平衡树不同(平衡树根本不允许有很长的路径),左偏树尽大约一半的可能保留了这个长度,并将它甩向左侧,利用它来缩短节点的距离以提高性能。这里我们不进行严格的讨论,左偏树作为一个例子大致告诉我们:放弃已有的信息意味着算法性能上的牺牲。下面是最好的左偏树:有序表(插入操作是按逆序发生的,自然的有序性被保留了)和最坏的左偏树:平衡树(插入操作是按正序发生的,自然的有序性完全被放弃了)。

1 2 2

3 4

5 6 7

有序表

平衡树

1 3 4 6 7 5

第 12 页 共 21 页

IOI2005国家集训队论文 黄源河

四、左偏树的应用

4.1 例——数字序列(Baltic 2004) [问题描述]*

给定一个整数序列a1, a2, … , an,求一个不下降序列b1 ≤ b2 ≤ … ≤ bn,使得数列{ai}和{bi}的各项之差的绝对值之和 |a1 - b1| + |a2 - b2| + … + |an - bn| 最小。 [数据规模] 1 ≤ n ≤ 106, 0 ≤ ai ≤ 2*109 [初步分析]

我们先来看看两个最特殊的情况:

1.a[1]≤a[2]≤…≤a[n],在这种情况下,显然最优解为b[i]=a[i];

2.a[1]≥a[2]≥…≥a[n],这时,最优解为b[i]=x,其中x是数列a的中位数?。 于是我们可以初步建立起这样一个思路: 把1…n划分成m个区间:[q[1],q[2]-1],[q[2],q[3]-1],??,[q[m],q[m+1]-1]?。每个区间对应一个解,b[q[i]] = b[q[i]+1] = … = b[q[i+1]-1] = w[i],其中w[i] 为a[q[i]], a[q[i]+1], ... , a[q[i+1]-1] 的中位数。

显然,在上面第一种情况下m=n,q[i]=i;在第二种情况下m=1,q[1]=1。 这样的想法究竟对不对呢?应该怎样实现?

若某序列前半部分a[1], a[2], … , a[n] 的最优解为 (u,u,…,u),后半部分a[n+1], a[n+2], ... , a[m] 的最优解为 (v,v,…,v),那么整个序列的最优解是什么呢?若u≤v,显然整个序列的最优解为 (u,u,…,u,v,v,…,v)。否则,设整个序列的最优解为 (b[1],b[2],…,b[m]),则显然b[n]≤u(否则我们把前半部分的解 (b[1],b[2],…,b[n]) 改为 (u,u,…,u),由题设知整个序列的解不会变坏),同理b[n+1]≥v。接下来,我们将看到下面这个事实:

对于任意一个序列a[1],a[2],…,a[n],如果最优解为 (u,u,…,u),那么在满足u≤u′≤b[1] 或b[n]≤u′≤u的情况下,(b[1],b[2],…,b[n]) 不会比 (u′,u′,…,u′) 更优。

我们用归纳法证明u≤u′≤b[1] 的情况,b[n]≤u′≤u的情况可以类似证明。 当n=1时,u=a[1],命题显然成立。 当n>1时,假设对于任意长度小于n的序列命题都成立,现在证明对于长度为n的序列命题也成立。首先把 (b[1], b[2], … b[n]) 改为 (b[1], b[1], … b[1]),这一改动将不会导致解变坏,因为如果解变坏了,由归纳假设可知a[2],a[3],…,a[n]的中位数w>u,这样的话,最优解就应该为(u,u,…,u,w,w,…,w),矛盾。然后我们再把(b[1],b[1],…,b[1])改为 (u′,u′,…,u′),由于| a[1] - x | + | a[2] - x | + … + | a[n] - x | 的几何意义为数轴上点x到点a[1], a[2], … a[n]的距离之和,且

*?

题目来源:Baltic OI 2004 Day 1, Sequence 本文对原题略微做了改动

为了方便讨论和程序实现,本文中提到的中位数,都是指数列中第?n/2?大的数 ?

这里我们认为q[m+1] = n+1

第 13 页 共 21 页

IOI2005国家集训队论文 黄源河

u≤u′≤b[1],显然点u′到各点的距离之和不会比点b[1]到各点的距离之和大,也就是说,(b[1],b[1],…,b[n]) 不会比 (v,v,…,v) 更优。(证毕) 再回到之前的论述,由于b[n]≤u,作为上述事实的结论,我们可以得知,将(b[1],b[2],…,b[n])改为(b[n],b[n],…,b[n]),再将(b[n+1],b[n+2],…,b[m])改为(b[n+1],b[n+1],…,b[n+1]),并不会使解变坏。也就是说,整个序列的最优解为(b[n],b[n],…,b[n],b[n+1],b[n+1],…,b[n+1])。再考虑一下该解的几何意义,设整个序列的中位数为w,则显然令b[n]=b[n+1]=w将得到整个序列的最优解,即最优解为 (w,w,…,w)。

分析到这里,我们一开始的想法已经有了理论依据,算法也不难构思了。 [算法描述]

延续我们一开始的思路,假设我们已经找到前k个数a[1], a[2], … , a[k] (kw[m+1],我们需要将最后两个区间合并,并找出新区间的最优解(也就是序列a中,下标在这个新区间内的各项的中位数)。重复这个合并过程,直至w[1]≤w[2]≤…≤w[m]时结束,然后继续处理下一个数。

这个算法的正确性前面已经论证过了,现在我们需要考虑一下数据结构的选取。算法中涉及到以下两种操作:合并两个有序集以及查询某个有序集内的中位数。能较高效地支持这两种操作的数据结构有不少,一个比较明显的例子是二叉检索树(BST),它的询问操作复杂度是O(logn),但合并操作不甚理想,采用启发式合并,总时间复杂度为O(nlog2n)。

有没有更好的选择呢?通过进一步分析,我们发现,只有当某一区间内的中位数比后一区间内的中位数大时,合并操作才会发生,也就是说,任一区间与后面的区间合并后,该区间内的中位数不会变大。于是我们可以用最大堆来维护每个区间内的中位数,当堆中的元素大于该区间内元素的一半时,删除堆顶元素,这样堆中的元素始终为区间内较小的一半元素,堆顶元素即为该区间内的中位数。考虑到我们必须高效地完成合并操作,左偏树是一个理想的选择*。左偏树的询问操作时间复杂度为O(1),删除和合并操作时间复杂度都是O(logn),而询问操作和合并操作少于n次,删除操作不超过n/2次(因为删除操作只会在合并两个元素个数为奇数的堆时发生),因此用左偏树实现,可以把算法的时间复杂度降为O(nlogn)。 [小结]

这道题的解题过程对我们颇有启示。在应用左偏树解题时,我们往往会觉得题目无从下手,甚至与左偏树毫无关系,但只要我们对题目深入分析,加以适当的转化,问题终究会迎刃而解。这需要我们具有敏捷的思维以及良好的题感。

用左偏树解本题,相比较于前面BST的解法,时间复杂度和编程复杂度更低,这使我们不得不感叹于左偏树的神奇威力。这不是说左偏树就一定是最好的解法,就本题来说,解法有很多种,光是可并堆的解法,就可以用多种数据结构来实现,但左偏树相对于它们,还是有一定的优势的,这将在下一章详细讨论。

*

前面介绍的左偏树是最小堆,但在本题中,显然只需把左偏树的性质稍做修改,就可以实现最大堆了

第 14 页 共 21 页

IOI2005国家集训队论文 黄源河

五、左偏树与各种可并堆的比较

我们知道,左偏树是一种可并堆的实现。但是为什么我们要用左偏树实现可并堆呢?左偏树相对于其他可并堆有什么优点?本章将就这个问题展开讨论,介绍各种可并堆的特点,并对它们做出比较。 5.1 左偏树的变种——斜堆

这里我们要介绍左偏树的一个变种——斜堆(Skew Heap)。斜堆是一棵堆有序的二叉树,但是它不满足左偏性质,或者说,斜堆根本就没有“距离”这个概念——它不需要记录任何一个节点的距离。从结构上来说,所有的左偏树都是斜堆,但反之不然。

类似于左偏树,斜堆的各种操作也是在合并操作的基础上完成的,因此这里只介绍斜堆的合并操作,其他操作读者都可以仿照左偏树完成。

斜堆合并操作的递归合并过程和左偏树完全一样。假设我们要合并A和B两个斜堆,且A的根节点比B的根节点小,我们只需要把A的根节点作为合并后新堆的根节点,并将A的右子树与B合并。由于合并都是沿着最右路径进行的,经过合并之后,新堆的最右路径长度必然增加,这会影响下一次合并的效率。为了解决这一问题,左偏树在进行合并的同时,检查最右路径节点的距离,并通过交换左右子树,使整棵树的最右路径长度非常小。然而斜堆不记录节点的距离,那么应该怎样维护最右路径呢?我们采取的办法是,从下往上,沿着合并的路径,在每个节点处都交换左右子树。

下面是斜堆合并操作的代码:

Function Merge(A,B) If A = NULL Then return B If B = NULL Then return A If key(B) < key(A) Then swap(A,B) right(A) ← Merge(right(A), B) swap(left(A), right(A)) return A End Function

斜堆的这种维护方法也是行之有效的。通过不断交换左右子树,斜堆把最右路径甩向左边了。可以证明,斜堆合并操作的平摊时间复杂度为O(logn)。这里略去详细的复杂度分析,感兴趣的读者可以自行参考相关的资料。

前面说过,斜堆的其他各种操作都和左偏树类似,因此斜堆各项操作的平摊时间复杂度都与左偏树相同。在空间上,由于斜堆不用记录节点的距离,因此它比左偏树的空间需求小一点。至于编程复杂度,两者都十分的低,不过斜堆的代码还是要比左偏树稍微简洁一些。至于斜堆的不足,大概可以算是它单次合并操

第 15 页 共 21 页