堆结构是一种隐式数据结构（implicit data structure），用完全二叉树表示的堆在数

组中是隐式存贮的（即没有明确的指针或其他数据能够重构这种结构）。由于没有存贮结构信

息，这种描述方法空间利用率很高，事实上没有空间浪费。尽管堆结构的时间和空间效率都

很高，但它不适合于所有优先队列的应用，尤其是当需要合并两个优先队列或多个长度不同

的队列时。因此需要借助于其他数据结构来实现这类应用，左偏树（ leftist tree）就能满足这

种要求。

左倾树是一种二叉树，它的节点除了和二叉树的节点一样具有左右子树指针（left、right）外，还有两个属性：键值和距离（dist）。键值上面已经说过，是用于比较节点的大小。距离则是如下定义的：

一个具有空左子树或空右子树的节点称为外节点；一个节点的距离是这个节点到最近的外节点所经过的边的数目（最近的意思是边的数目最小），特别的，如果一个节点本身是外节点，则它的距离为0；而空节点的距离规定为-1（后面将会看到这样规定的理由）。在本文中，有时也提到一棵树的距离，这是指该树根节点的距离。

左倾树的各个属性满足下面两条性质：

1. 一个节点的键值小于或等于它的左右子节点的键值（如果有子节点的话）。

2. 一个节点的左子节点的距离大于或等于右子节点的距离。

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

不难看到，左倾树的根节点是树中所有节点里键值最小的，它的每一棵子树也具有这样的性质。这样的性质称为堆性质，具有堆性质的数据结构称为堆（heap）。因此左倾树是一种堆。堆是实现优先队列的很好的数据结构，因为我们可以立即取到堆中的最小元素。

Leftise Tree主要有以下关键操作

1. PopMin（取出最小节点）

2. Merge(a,b)（合并分别以a和b为根的树）

3. Insert(v)（插入值为v的新节点）

以上操作的复杂度均为Θ(lg n)。

Merge是最关键的操作，通过递归调用来实现，具体思想是：如果a的键值小于b的键值，那么合并a的右枝与b，否则合并a与b的右枝，直到其一为空。但是这样的合并操作有可能打破了左偏树的性质2，这时只要交换根的左枝和右枝即可，并更新根节点的高度。

Insert过程可以视为将只有一个新节点的树与原树合并，初始化一棵新树后调用Merge即可。

Popmin过程中取出根节点的键值，然后合并左右子树，将得到的根作为新的根即可。

关于复杂度的保证可以参见左偏树的这一定理：若一棵左偏树有N个节点，则该左偏树的距离不超过 [log(N+1) ]-1。

而Merge过程只会沿两棵树的最右路径进行，显然复杂度是Θ(lg n)的。