2024年4月12日发(作者：)

IOI2005国家集训队论文 黄源河

左偏树的特点及其应用

广东省中山市第一中学 黄源河

【摘要】

本文较详细地介绍了左偏树的特点以及它的各种操作。

第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分

主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并

给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中

的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应

用前景。

【关键字】

左偏树 可并堆 优先队列

【目录】

一、引言 ................................................................................................................................... 2

二、左偏树的定义和性质 ....................................................................................................... 2

2.1 优先队列，可并堆 .................................................................................................... 2

2.1.1 优先队列的定义 ............................................................................................. 2

2.1.2 可并堆的定义 ................................................................................................. 2

2.2 左偏树的定义 ............................................................................................................ 3

2.3 左偏树的性质 ............................................................................................................ 4

三、左偏树的操作 ................................................................................................................... 5

3.1 左偏树的合并 ............................................................................................................ 5

3.2 插入新节点 ................................................................................................................ 7

3.3 删除最小节点 ............................................................................................................ 8

3.4 左偏树的构建 ............................................................................................................ 8

3.5 删除任意已知节点 .................................................................................................... 9

3.6 小结 .......................................................................................................................... 12

四、左偏树的应用 ................................................................................................................. 13

4.1 例——数字序列（Baltic 2004） ........................................................................... 13

五、左偏树与各种可并堆的比较 ......................................................................................... 15

5.1 左偏树的变种——斜堆 .......................................................................................... 15

5.2 左偏树与二叉堆的比较 .......................................................................................... 16

5.3 左偏树与其他可并堆的比较 .................................................................................. 16

六、总结 ................................................................................................................................. 18

第 1 页 共 21 页

IOI2005国家集训队论文 黄源河

【正文】

一、引言

优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪

心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优

先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉

堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。

二、左偏树的定义和性质

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

2.1 优先队列，可并堆

2.1.1 优先队列的定义

优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面

有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含

一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假

设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优

先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除

最小节点(Delete-Min)。

2.1.2 可并堆的定义

可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三

个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作：

H ← Merge(H

1

,H

2

)

Merge( ) 构造并返回一个包含H

1

和H

2

所有元素的新堆H。

前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合

并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法

的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci

Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可

并堆的比较。

第 2 页 共 21 页