1.3　左倾堆

前面介绍过堆，当需要合并两个堆时，往往效率较低。本节介绍的左倾堆能高效地实现两个堆的合并，称之为可并堆。左倾堆又称为左偏树、左偏堆、最左堆等。

1.3.1　左倾堆相关定义和性质

零距离（Null Path Length，NPL）是指从一个节点到一个“最近的不满节点”的路径长度。不满节点是指该节点的左、右子节点至少有一个为空。叶子节点的NPL为0；空节点的NPL为-1。

在左倾堆中的每个节点均维护两个值—键值和零距离。左倾堆满足：

（1）节点的键值小于或等于它的子节点的键值，即堆性质。

（2）节点的左子节点的NPL大于或等于右子节点的NPL，即左倾性质。

（3）节点的NPL等于它的右子节点的NPL+1。

（4）左倾堆的任意子树也是左倾堆。

1.3.2　左倾堆的操作

（1）两个左倾堆的合并。将A和B两个左倾堆合并为C，如果其中一个为空，只需返回另一棵树即可；当A和B都为非空时，假设A的根节点小于等于B的根节点（否则交换A、B），把A的根节点作为新树C的根节点，然后合并A的右子树和B，之后右子树的NPL可能会变大，当A的右子树的NPL大于其左子树的NPL时，左倾堆的左倾会被破坏。在这种情况下，只需要交换左、右子树。最后，由于A的右子树的NPL可能发生改变，必须更新A的NPL：NPL（A）←NPL（A的右子树）+1。

（2）插入新节点。单个节点也可以看成一个左倾堆，因此向左倾堆插入一个节点可以看成两个左倾堆的合并。

（3）删除最小节点。左倾堆的根节点就是最小节点，在删除根节点后，需要将两棵子树合并。

左倾堆的实现如下所述。

1.3.3　例题讲解

例1-2　Financial Fraud

Time Limit:3000 ms　Memory Limit:65536 KB

题目描述：

给定一个整数序列A1,A2,…,AN，求一个非递减序列B1,B2,…,BN（1≤i<j≤N，Bi≤Bj），使得风险值最小，即|A1-B1|+|A2-B2|+…+|AN-BN|最小。

输入：

第一行输入N（N≤50000），第二行输入N个整数表示序列A（-109≤Ai≤109），N等于0时结束输入。

输出：

最小风险值。

样例输入：

4

300 400 200 100

0

样例输出：

400

题目来源：ZOJ3512。

解题思路：

当A是一个非递减序列时，只需让Bi=Ai即可；当A是一个非递增序列时，最优解是让B1=B2=…=BN=序列A的中位数（中位数是指序列中第N/2大的数）；当A不是以上两种特殊情况时，可以考虑把序列A分为一些区间段，相对应的序列B为那一段的中位数。

假设已经找到前k个数A1,A2,…,Ak（k<N）的最优解，需要求前k+1个数的最优解。先把第k+1个数单独作为一个区间，则中位数就是Ak+1，因为要求B是非递减序列，如果Ak+1大于或等于前一个区间的中位数，就保留Ak+1作为单独一个区间；否则，需要将Ak+1和前一个区间合并。

因为涉及区间合并，很容易想到本节介绍的可合并堆—左倾堆。如何用左倾堆维护区间中位数呢？只需要用大顶堆维护区间较小的一半元素，这样堆顶元素就是中位数。在每次从左向右求解时，可把每一个数单独建一个左倾堆，如果当前区间的中位数小于前一个区间的中位数时，就将两个左倾堆合并，并弹出堆顶多余的元素。

题目实现：