优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。

左偏树的定义和性质

在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。

优先队列，可并堆

优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质:有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作:插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。

可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum,Delete-Min)，还支持一个额外的操作--合并操作:

[性质1] 节点的键值小于或等于它的左右子节点的键值。

即key(i)≤key(parent(i)) 这条性质又叫堆性质。符合该性质的树是堆有序的(Heap-Ordered)。有了性质1，我们可以知道左偏树的根节点是整棵树的最小节点，于是我们可以在O(1) 的时间内完成取最小节点操作。

[性质2] 节点的左子节点的距离不小于右子节点的距离。

即dist(left(i))≥dist(right(i)) 这条性质称为左偏性质。性质2是为了使我们可以以更小的代价在优先队列的其它两个基本操作(插入节点、删除最小节点)进行后维持堆性质。在后面我们就会看到它的作用。

这两条性质是对每一个节点而言的，因此可以简单地从中得出，左偏树的左右子树都是左偏树。

由这两条性质，我们可以得出左偏树的定义:左偏树是具有左偏性质的堆有序二叉树。

我们知道，一个节点必须经由它的子节点才能到达外节点。由于性质2，一个节点的距离实际上就是这个节点一直沿它的右边到达一个外节点所经过的边数，也就是说，我们有

[性质3] 节点的距离等于它的右子节点的距离加1。

即dist( i ) = dist( right( i ) ) + 1 外节点的距离为0，由于性质2，它的右子节点必为空节点。为了满足性质3，故前面规定空节点的距离为-1。

我们的印象中，平衡树是具有非常小的深度的，这也意味着到达任何一个节点所经过的边数很少。左偏树并不是为了快速访问所有的节点而设计的，它的目的是快速访问最小节点以及在对树修改后快速的恢复堆性质。从图中我们可以看到它并不平衡，由于性质2的缘故，它的结构偏向左侧，不过距离的概念和树的深度并不同，左偏树并不意味着左子树的节点数或是深度一定大于右子树。

下面我们来讨论左偏树的距离和节点数的关系。

[引理1] 若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。

证明:由性质2可知，当且仅当对于一棵左偏树中的每个节点i，都有dist(left(i)) =dist(right(i)) 时，该左偏树的节点数最少。显然具有这样性质的二叉树是完全二叉树。

[定理1] 若一棵左偏树的距离为k，则这棵左偏树至少有2^(k+1)-1个节点。

证明:由引理1可知，当这样的左偏树节点数最少的时候，是一棵完全二叉树。距离为k的完全二叉树高度也为k，节点数为2^(k+1)-1，所以距离为k的左偏树至少有2^(k+1)-1个节点。

作为定理1的推论，我们有:

[性质4] 一棵N个节点的左偏树距离最多为ëlog(N+1)û-1。

证明:设一棵N个节点的左偏树距离为k，由定理1可知，N ≥ 2^(k+1)-1，因此k ≤ ëlog(N+1)û-1。

标程

《数字序列》程序