本节书摘来自华章计算机《程序设计解题策略》一书中的第1章，第1.6节,作者：吴永辉　王建德 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.6　利用左偏树实现优先队列的合并

优先队列在程序设计竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单、效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。为了解决这个问题，我们引入了左偏树。
1.6.1　左偏树的定义和性质
在介绍左偏树之前，我们先来回顾一下优先队列和可并堆的概念。
优先队列(priority queue)：一种抽象数据类型(ADT)。它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见，我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)、取得最小节点(Minimum)和删除最小节点(Delete-Min)。
可并堆(mergeable heap)：也是一种抽象数据类型，它除了支持优先队列的三个基本操作，还支持一个额外的操作——合并操作：H=Merge(H1，H2)，该操作构造并返回一个包含H1和H2所有元素的新堆H。
左偏树(leftist tree)：一种可并堆的实现。左偏树是一棵二叉树，它的节点除了和二叉树的节点一样具有左右子树指针(left，right)外，还有两个属性：键值和距离(dist)。键值是用于比较节点的大小，而距离是在外节点的基础上提出的。距离和外节点的定义：
外节点(external node)：节点i称为外节点当且仅当节点i的左子树或右子树为空(left(i)=NULL或right(i)=NULL)。
节点i的距离(Dist(i))：节点i到它的后代中，最近的外节点所经过的边数。特别地，如果节点i本身是外节点，则它的距离为0；而空节点的距离规定为-1(Dist(NULL)=-1)。左偏树的距离指的是该树根节点的距离。
左偏树的定义是由其本身具备的两个基本特征引出的：
堆特征：节点的键值小于或等于它的左右子节点的键值，即key(i)≤key(parent(i))。符合堆特征的树是堆有序的(heap-ordered)。有了堆特征，我们可以知道左偏树的根节点是整棵树的最小节点，于是我们可以在O(1)的时间内完成取最小节点操作。
左偏特征：节点的左子节点的距离不小于右子节点的距离，即Dist(left(i))≥Dist(right(i))。
左偏特征是为了使我们在插入节点和删除最小节点后，以更小的代价维持堆特征。在后面我们就会看到它的作用。
由于左偏树的每一个节点具有堆特征和左偏特征，因此左偏树任一节点的左右子树都是左偏树。由堆特征和左偏特征可以引出左偏树的定义：（左偏树是具有左偏特征的堆有序二叉树）。
图1.6-1是一棵左偏树。

下面，我们来分析左偏树的性质。我们知道，左偏树的任一个非叶节点必须经由它的子节点才能到达外节点。由于左偏特征，一个节点的距离实际上就是这个节点一直沿它的右边到达一个外节点所经过的边数，因此引出：
【性质1.6-1】　节点的距离等于它的右子节点的距离加1，即Dist(i)=Dist(right(i))+1。
外节点的距离为0，由于左偏特征，它的右子节点必为空节点。为了满足性质1.6-1，故前面规定空节点的距离为-1。
在我们的印象中，平衡树是具有非常小的深度的，这也意味着到达任何一个节点所经过的边数很少。左偏树并不是为了快速访问所有节点而设计的，它的目的是快速访问最小节点以及在对树修改后快速恢复堆特征。从图1.6-1中我们可以看到它并不平衡，由于左偏特征的缘故，它的结构偏向左侧，不过距离的概念和树的深度并不同，左偏树并不意味着左子树的节点数或是深度一定大于右子树。下面，我们来讨论左偏树的距离和节点数的关系。
【引理1.6-1】　若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。
证明：由左偏特征可知，当且仅当对于一棵左偏树中的每个节点i，都有Dist(left(i))=Dist(right(i))时，该左偏树的节点数最少。显然具有这样性质的二叉树是完全二叉树。
【定理1.6-1】　若一棵左偏树的距离为k，则这棵左偏树至少有2k+1-1个节点。
证明：由引理1.6-1可知，当这样的左偏树节点数最少的时候，是一棵完全二叉树。距离为k的完全二叉树高度也为k，节点数为2k+1-1，所以距离为k的左偏树至少有2k+1-1个节点。
作为定理1.6-1的推论，我们有：
【性质1.6-2】　一棵N个节点的左偏树距离最多为log2(N+1)」-1。
证明：设一棵N个节点的左偏树距离为k，由定理1.6-1可知，N≥2k+1-1，因此k≤log2(N+1)」-1。
有了左偏树的堆特征、左偏特征和上面两个性质，我们可以开始讨论左偏树的操作了。
1.6.2　左偏树的操作
首先，我们定义左偏树节点的数据结构。设：

struct node;
typedef node *leftlist;// 左偏树的指针类型
struct node{// 左偏树的节点类型
int key, Dist;// 键值和距离
leftlist left, right，parent;// 左右指针和父指针
};
leftlist tree［MAXN］;// 左偏树

左偏树的操作包括构建左偏树、合并左偏树、插入新节点、删除最小节点和删除任意节点。
1.构建左偏树
将n个节点构建成一棵左偏树，这也是一个常用的操作。构建方法有两种：
构建方法1：逐个节点插入，时间复杂度为O(nlog2n)。
构建方法2：仿照二叉堆的构建算法，图1.6-2给出了范例。

下面分析算法的时间复杂度。假设n=2k，则：
前n2次合并的是两棵只有1个节点的左偏树。
接下来的n4次合并的是两棵有2个节点的左偏树。
接下来的n8次合并的是两棵有4个节点的左偏树。
……
接下来的n2i次合并的是两棵有2i-1个节点的左偏树。
合并两棵2i个节点的左偏树时间复杂度为O(i)，因此算法总的时间复杂度为

n2*O(1)+n4*O(2)+n8*O(3)+…=On*∑ki=1i2i=On*2-k+22k=O(n)。

2.合并左偏树(Merge(A，B))
由于合并操作是插入和删除操作的基础，因此我们做重点讨论：
Merge(A，B)把A、B两棵左偏树合并，返回一棵包含A和B中所有元素的左偏树C。一棵左偏树用它的根节点的指针表示(见图1.6-3)。
在合并操作中，最简单的情况是其中一棵树为空(也就是，该树根节点指针为NULL)。这时我们只需要返回另一棵树。
若A和B都非空，我们假设A的根节点小于等于B的根节点(否则交换A、B)，把A的根节点作为新树C的根节点，剩下的事就是合并A的右子树right(A)和B了(见图1.6-4)。
合并了right(A)和B之后，right(A)的距离可能会变大，当right(A)的距离大于left(A)的距离时，左偏树的左偏特征会被破坏(见图1.6-5)。在这种情况下，我们只须交换left(A)和right(A)。

最后，由于right(A)的距离可能发生改变，我们必须更新A的距离：

Dist(A)=Dist(right(A))+1

不难验证，经这样合并后的树C符合堆特征和左偏特征，因此是一棵左偏树。至此左偏树的合并就完成了。图1.6-6是一个合并过程的范例(节点上方的数字为距离值)。

leftlist Merge(leftlist a, leftlist b)// 合并以a和b为根的两棵左偏树，返回合并后的新树根
{
leftlist temp;
if (a == NULL) return b;// 若其中一棵左偏树为空,则返回另一棵
if (b == NULL) return a;
if (b->key < a->key)　{ temp=a;a=b;b=temp; 
// 假设a的数据值不大于b的数据值。把a作为新树根，其右子树为为原a的右子树与b的合并
a->r=Merge(a->r, b);
if ((a->left==NULL)||((a->r!=NULL)&&(a->r->Dist> a->left->Dist)))
// 若a的右子树空或者a的右子树的距离大于左子树的距离，则交换左右子树，以维护左偏树的左偏性质 
{ temp=a->Right;a->Right=a->left;a->left=temp;}
if (a->Right==NULL)　a->Dist=0 ;// 更新a的距离
else a->Dist=a->Right->Dist+1; 
return a;// 返回合并后的左偏树
}

下面分析合并操作的时间复杂度。由上所述，每一次递归合并的开始，都需要分解其中一棵树，总是把分解出的右子树参加下一步的合并。根据性质1.6-1，一棵树的距离决定于其右子树的距离，而右子树的距离在每次分解中递减，因此每棵树A或B被分解的次数分别不会超过它们各自的距离。根据性质1.6-2，分解的次数不会超过log2(N1+1)」+log2(N2+1)」-2，其中N1和N2分别为左偏树A和B的节点个数。因此合并操作最坏情况下的时间复杂度为O(log2(N1+1)」+log2(N2+1)」-2)=O(log2N1+log2N2)。

3.插入节点(Insert(val))
单节点的树一定是左偏树，因此向左偏树插入一个值为val的节点可以看作是对两棵左偏树的合并(见图1.6-7)。
下面是插入新节点的代码：

leftlist Insert( int val)// 向左偏树插入值为val的一个节点，返回新树根
{
构造一个数据值为val的单节点newNode(newNode->left=newNode->Right=newNode->parent=
null， newNode->Dist=0；newNode->key=val)；
root=Merge(root， newNode);// newNode并入以root为根的左偏树，返回根root
return root;
}

由于合并的其中一棵树只有一个节点，因此插入新节点操作的时间复杂度是O(log2n)。
4.删除左偏树的最小节点(DeleteRoot())
由堆特征，我们知道，左偏树的根节点是最小节点。在删除根节点后，剩下的两棵子树都是左偏树，需要把它们合并(见图1.6-8)。

删除最小节点操作的代码也非常简单：

void Deleteroot(leftlist &a)// 删除左偏树a的根节点，返回新树根a
{ a=Merge(a->left， a-> right); }// 合并左右子树，合并后的根节点为a

由于删除最小节点后只需进行一次合并，因此删除最小节点的时间复杂度也为O(log2n)。
5.删除任意已知节点x(Delete(x))
我们在这里之所以强调“已知”，是因为任意节点x并不是根据它的键值找出来的，左偏树本身除了可以迅速找到最小节点外，不能有效地搜索指定键值的节点。例如不能要求删除所有键值为100的节点。
前面说过，优先队列是一种容器。对于通常的容器来说，一旦节点被放进去以后，容器就完全拥有了这个节点，每个容器中的节点具有唯一的对象掌握它的拥有权(ownership)。对于这种容器的应用，优先队列只能删除最小节点，因为你根本无从知道它的其他节点是什么。
但是优先队列除了作为一种容器外还有另一个作用，就是可以找到最小节点。很多应用是针对这个功能的，它们并没有将拥有权完全转移给优先队列，而是把优先队列作为一个最小节点的选择器，从一堆节点中依次将它们选出来。这样一来节点的拥有权就可能同时被其他对象掌握。也就是说某个节点虽不是最小节点，不能从优先队列那里“已知”，但却可以从其他的拥有者那里“已知”。
这种优先队列的应用也是很常见的。设想我们有一个闹钟，它可以记录很多个响铃时间，不过由于时间是线性的，铃只能一个个按先后次序响，优先队列就很适合用来做这样的挑选。另一方面使用者应该可以随时取消一个“已知”的响铃时间，这就需要进行任意已知节点的删除操作了。
我们的这种删除操作需要指定被删除的节点，这和原来删除根节点的操作是兼容的，因为根节点肯定是已知的。上面已经提过，在删除一个节点以后，将会剩下它的两棵子树，它们都是左偏树，我们先通过p=Merge(left(x)，right(x))把它们合并成一棵新的左偏树。现在p指向了这棵新的左偏树，如果我们删除的是根节点，此时任务已经完成了。不过，如果被删除节点x不是根节点就有点麻烦了。这时p指向的新树的距离有可能比原来x的距离要大或小，这势必有可能影响原来x的父节点q的距离，因为q现在成为新树p的父节点了。于是就要仿照合并操作里面的做法，对q的左右子树作出调整，并更新q的距离。这一过程引起了连锁反应，我们要顺着q的父指针链一直往上进行调整(见图1.6-9)。
新树p的距离为Dist(p)，如果Dist(p)+1等于q的原有距离Dist(q)，那么不管p是q的左子树还是右子树，我们都不需要对q进行任何调整，此时删除操作也就完成了。
如果Dist(p)+1小于q的原有距离Dist(q)，那么q的距离必须调整为Dist(p)+1，而且如果p是左子树的话，说明q的左子树距离比右子树小，必须交换子树。由于q的距离减少了，所以q的父节点也要做出同样的处理。

剩下就是另外一种情况了，p的距离增大了，使得Dist(p)+1大于q的原有距离Dist(q)。在这种情况下，如果p是左子树，那么q的距离不会改变，此时删除操作也可以结束了。如果p是右子树，这时有两种可能：一种是p的距离仍小于等于q的左子树距离，这时我们直接调整q的距离就行了；另一种是p的距离大于q的左子树距离，这时我们需要交换q的左右子树并调整q的距离，交换完了以后q的右子树是原来的左子树，它的距离加1只能等于或大于q的原有距离，如果等于成立，删除操作可以结束了，否则q的距离将增大，我们还要对q的父节点做出相同的处理。删除任意已知节点操作的代码如下：

void Delete(leftlist node)　　　　　　　　　// 在左偏树中删除任意已知节点node
{
q=node->parent;// 计算node的父节点q
p=Merge(node->left,node->right);// 将node的左右子树合并成一棵新的左偏树p
p->parent=q;// q成为新树p的父节点。
If(q≠NULL)&&( q->left=node)q->left=p// 按原树结构确定p是q的左儿子或右儿子
If(q≠NULL)&&( q->right=node) q->right=p;
While q≠NULL Do// 顺着q的父节点链往上调整
{ If(q->left->Dist<q->right->Dist) q->left和q->right交换;
// 若q的右子树距离大于q的左子树距离，则交换q的左右子树
If(q->right->Dist+1=q->Dist)Exit;// 如果q的右子树距离+1等于q的原有距离，则删除操作完成
q->Dist=q->right->Dist+1;// q的距离调整为q的右子树距离+1
p=q;q=q->parent;// 顺着q的父节点链往上调整
}
};

下面分两种情况讨论删除操作的时间复杂度。
情况1：p的距离减小了。在这种情况下，由于q的距离只能缩小，当循环结束时，要么根节点处理完了，q为空；要么p是q的右子树并且Dist(p)+1=Dist(q)。如果Dist(p)+1>Dist(q)，那么p一定是q的左子树，否则会出现q的右子树距离缩小了，但是加1以后却大于q的距离的情况，不符合左偏树的性质1。不论哪种情况，删除操作都可以结束了。注意到，每一次循环，p的距离都会加1，而在循环体内，Dist(p)+1最终将成为某个节点的距离。根据性质2，任何的距离都不会超过log2n，所以循环体的执行次数不会超过log2n。
情况2：p的距离增大了。在这种情况下，我们将必然一直从右子树向上调整，直至q为空或p是q的左子树时停止。一直从右子树升上来这个事实说明了循环的次数不会超过log2n(性质2)。
最后我们看到这样一个事实，这两种情况只会发生其中一种。如果某种情况的调整结束后，我们可以知道要么q为空，要么Dist(p)+1=Dist(q)。要么p是q的左子树。这三种情况都不会导致另一情况发生。直观上来讲，如果合并后的新子树导致了父节点的一系列距离调整的话，要么就一直是往小调整，要么是一直往大调整，不会出现交替的情况。
我们已经知道合并出新子树p的复杂度是O(log2n)，向上调整距离的复杂度也是O(log2n)，故删除操作的最坏情况的时间复杂度是O(log2n)。如果左偏树非常倾斜，实际应用情况下要比这个快得多。
由左偏树的各种操作可以看出，左偏树作为可并堆的实现，它的各种操作性能都十分优秀，且编程复杂度比较低，可以说是一个“性价比”十分高的数据结构。左偏树之所以是很好的可并堆实现，是因为它能够比较充分地利用堆中的有用信息，没有将这些信息浪费掉。根据堆特征，我们知道，从根节点向下到任何一个外节点的路径都是有序的。存在越长的路径，说明树的整体有序性越强，与平衡树不同(平衡树根本不允许有很长的路径)，左偏树尽大约一半的可能保留了这个长度，并将它甩向左侧，利用它来缩短节点的距离以提高性能。这里我们不进行严格的讨论。左偏树作为一个例子大致告诉我们：放弃已有的信息意味着算法性能上的牺牲。由于有序表的插入操作是按逆序发生的，保留了自然的有序性，因此是一种最好的左偏树；而平衡树的插入操作是按正序发生的，完全放弃了自然的有序性，因此是一种最坏的左偏树。图1.6-10分别列出了这两种“极端”的左偏树。

这里，需要声明的是，可用于可并堆的优先队列并非仅左偏树一种，二项堆(binomial heap)和fibonacci堆(fibonacci heap)都是十分优秀的可并堆。表1.6-1列出这些可并堆的时空效率。

由上表可以看出，这四种可并堆各有所长。虽然，左偏树在时间效率上不如二项堆和Fibonacci堆，在空间效率上不如二叉堆，但从“鱼与熊掌不可兼得”的角度看，这正是左偏树可利用的价值所在。因为在很多情况下，时间复杂度、空间复杂度和编程复杂度之间是矛盾的：Fibonacci堆时间复杂度最低，但编程复杂度让人无法接受；二叉堆的空间复杂度和编程复杂度都很低，但合并二叉堆的时间复杂度(O(n))却是致命弱点，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树在存储性质上，没有二叉堆那样的缺陷；作为二叉堆的一种替代品应用于各种优先队列，很多时候甚至比二叉堆更方便。由此可见，左偏树比较均衡地协调了时间复杂度、空间复杂度和编程复杂度之间的矛盾。
1.6.3　应用左偏树解题
若现实生活中的问题可转化为合并两个优先队列的数学模型，则采用左偏树解题是最为明智的选择。我们不妨通过一个范例来体验左偏树的应用价值。
【1.6.1　Financial Fraud】
【问题描述】
Bernard Madoff是一位美国的股票经纪人、投资顾问、NASDAQ股票市场的非执行董事长，并被认为是历史上最大的庞氏(Ponzi)骗局的操盘手。
两个程序员Jerome OHara和George Perez，帮助Bernard Madoff编写程序，产生虚假的记录，因而被指控涉嫌伪造代理经销商的记录和变造投资顾问的记录。
在这些年中每个季度，这两个程序员都会收到一个数据表，给出在这一时期的一系列的利润记录a1 a2 … aN。由于经济危机，这些可怕的记录可能会吓得投资者望而却步。所以，这两程序员被要求将这些记录变造为b1 b2 … bN。为了欺骗投资者，任何一项记录必定不能小于前面的记录(也就是说，对任意的1≤i在另一方面，他们为他们的非法工作定义了一个冒险值(risk value)：risk value=a1-b1+a2-b2+…+aN-bN。例如，原始的利润记录是300、400、200、100，如果他们选择300、400、400、400作为虚假记录，则冒险值是0+0+200+300=500。但如果他们选择250、250、250、250作为虚假记录，则冒险值是50+150+50+150=400。为了避免引起怀疑，他们需要最小化冒险值。
给出原始利润记录的一些拷贝，请你找出最小可能的冒险值。
输入：
输入有多个测试用例(至多20个)。
对每个测试用例，第一行给出一个整数N(1≤N≤50000)，下一行给出N个整数a1a2…aN(-109≤ai≤109)。输入以N=0结束。
输出：
对每个测试用例，输出一行，给出最小可能的冒险值。

试题解析
简述题意：给出含n(≤50000)个数的序列a［1］…a［n］，求一个非递减的序列b［1］…b［n］，使得∑ni=1a［i］-b［i］最小。
我们先来看看两个最特殊的情况：
特殊情况1：a［1］≤a［2］≤…≤a［n］，在这种情况下，显然最优解为b［i］=a［i］；
特殊情况2：a［1］≥a［2］≥…≥a［n］，这时，最优解为b［i］=x，其中x是数列a的中位数(为了方便讨论和程序实现，中位数都是指数列中第n/22」大的数)。
于是我们可以初步建立起这样一个思路：把1…n划分成m个区间，
［q［1］，q［2］-1］，［q［2］，q［3］-1］，…，［q［m］，q［m+1］-1］(q［i］为第i个区间的首指针，q［m+1］=n+1)
b序列中每个区间的元素值取a序列对应区间的中位数，即：
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。接下来，我们将看到下面这个事实：
【定理1.6-2】　对于任意一个序列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］的距离之和，且u≤u′≤b［1］，显然点u′到各点的距离之和不会比点b［1］到各点的距离之和大，也就是说，(b［1］，b［2］，…，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(log2n)，但合并操作不甚理想，采用启发式合并，总时间复杂度为O(nlog22n)。
有没有更好的选择呢？通过进一步分析，我们发现只有当某一区间内的中位数比后一区间内的中位数大时，合并操作才会发生；也就是说，任一区间与后面的区间合并后，该区间内的中位数不会变大。于是我们可以用最大堆来维护每个区间内的中位数，当堆中的元素大于该区间内元素的一半时，删除堆顶元素，这样堆中的元素始终为区间内较小的一半元素，堆顶元素即为该区间内的中位数。考虑到我们必须高效地完成合并操作，左偏树是一个理想的选择。虽然前面介绍的左偏树是最小堆，但在本题中，显然只需把左偏树的性质稍做修改，就可以实现最大堆了。左偏树的询问操作时间复杂度为O(1)，删除和合并操作时间复杂度都是O(log2n)，而询问操作和合并操作少于n次，删除操作不超过n/2次(因为删除操作只会在合并两个元素个数为奇数的堆时发生)，因此用左偏树实现，可以把算法的时间复杂度降为O(n*log2n)。
程序清单

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int MAXN =50050;// 整数序列的长度上限
struct node;
typedef node *leftlist;// 左偏树的指针类型
struct node{// 左偏树的节点类型
int key, Dist;// 键值和距离
leftlist l, r;// 左右指针
};
leftlist tree［MAXN］;// 左偏树
int size［MAXN］, s［MAXN］, t［MAXN］;// 第i棵左偏树的规模为size［i］；第i个区间的始末端点
// 为s［i］和t［i］
int a［MAXN］;// 整数序列
int m, n;// 整数序列的长度为n；区间个数为m 

void Init()// 输入整数序列
{
for(int i=1; i<=n;++i)cin>>a［i］;// 读整数序列
m=0;// 区间个数初始化
}

leftlist Merge(leftlist a, leftlist b)// 合并以a和b为根的两棵左偏树
{
leftlist temp;
if (a == NULL) return b;// 若其中一棵左偏树为空，则返回另一棵
if (b == NULL) return a;
if(b->key>a->key){temp=a;a=b;b=temp;}
// 假设a的根节点大于等于b的根节点，把a的根节点作为新树的根节点，合并a的右子树和b
a->r=Merge(a->r, b);
if((a->l==NULL)||((a->r!=NULL)&&(a->r->Dist>a->l->Dist)))
// 若a的右子树空或者a的右子树距离大于左子树距离，则交换左右子树，以维护左偏树的左偏性质 
{ temp=a->r;a->r=a->l;a->l=temp;}
if (a->r == NULL)　a->Dist=0 ;else a->Dist=a->r->Dist+1;
// 更新a的距离
return a;// 返回合并后的左偏树
}

void Delete(leftlist &a)// 删除左偏树a的根节点
{ a=Merge(a->l, a->r); }

void Make()// 计算和输出满足要求的不下降序列
{
int i, j, b;long long ans;
for (i=1; i <= n;++i)// 搜索整数序列的每个元素
{
tree［++m］=new node;// 为第i个整数新建一个区间
tree［m］->key=a［i］;tree［m］->Dist=0;
tree［m］->l=NULL;tree［m］->r=NULL;
size［m］=1;s［m］=i;t［m］=i;
while ((m>1)&&(tree［m-1］->key>=tree［m］->key))
// 如果当前区间的值小于前一个区间的值，则合并两个区间
{
tree［m-1］=Merge(tree［m-1］,tree［m］);size［m-1］=size［m-1］+size［m］;
t［m-1］=t［m］;--m;
while (size［m］>(t［m］-s［m］)/2+1)// 删除区间的后半部分
{ Delete(tree［m］);--size［m］; }
}
}
ans=0;// n项之差的绝对值之和的最小值初始化
for (i=1; i <= m; ++i)// 满足要求的不下降序列由每个区间的解构成
for(j=s［i］;j<=t［i］;++j)// 枚举a的第i个区间的所有整数，累计当前项之差的绝对值
ans+=abs(a［j］-tree［i］->key);
cout << ans << endl;// 输出n项之差的绝对值之和的最小值
}

int main()
{
while(1){
cin>>n;// 反复输入整数序列的长度，直至输入0为止
if(!n)break;
Init();// 输入整数序列
Make();// 计算和输出满足要求的不下降序列
}
return 0;
}