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] (k
这个算法的正确性前面已经论证过了，现在我们需要考虑一下数据结构的选取。算法中涉及到以下两种操作：合并两个有序集以及查询某个有序集内的中位数。能较高效地支持这两种操作的数据结构有不少，一个比较明显的例子是二叉检索树(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 页