算法合集之《左偏树的特点及其应用》.pdf

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
四、左偏树的应用.....................................................................