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

左偏树的定义和性质

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

优先队列，可并堆

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

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