IOI2005

国家集训队论文

黄源河

第

1 

页

共

21 

页

左

偏

树

的

特

点

及

其

应

用

广东省中山市第一中学

黄源河

【摘要】

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

第一部分提出可并堆的概念，

指出二叉堆的不足，

并引出左偏树。

第二部分

主要介绍了左偏树的定义和性质。

第三部分详细地介绍了左偏树的各种操作，

并

给出时间复杂度分析。

第四部分通过一道例题，

说明左偏树在当今信息学竞赛中

的应用。

第五部分对各种可并堆作了一番比较。

最后总结出左偏树的特点以及应

用前景。

【关键字】

左偏树

可并堆

优先队列

【目录】

一、引言

.

.................................................................................................................................. 

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 

小结

.

......................................................................................................................... 

1

2 

四、左偏树的应用

.

................................................................................................................ 

1

3 

4.1 

例

——

数字序列（

Baltic 2004

）

 ........................................................................... 

1

3 

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

.

........................................................................................ 

1

5 

5.1 

左偏树的变种——斜堆

.

......................................................................................... 

1

5 

5.2 

左偏树与二叉堆的比较

.

......................................................................................... 

1

6 

5.3 

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

.

................................................................................. 

1

6 

六、总结

.

................................................................................................................................ 

1

8