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

本资料由-HYPERLINK"http://www.chuangyw.com/"大学生创业|HYPERLINK"http://www.chuangyw.com/"创业|HYPERLINK"http://www.chuangyw.com/"创业网http://www.chuangyw.com/提供资料

HYPERLINK"http://www.dailiav.com/"在线代理|HYPERLINK"http://www.dailiav.com/"网页代理|HYPERLINK"http://www.dailiav.com/"代理网页|http://www.dailiav.comHYPERLINK"http://pigproxy.cn"减肥药排行榜|HYPERLINK"http://pigproxy.cn"淘宝最好的减肥药|HYPERLINK"http://pigproxy.cn"什么减肥药效果最好|HYPERLINK"http://pigproxy.cn"减肥瘦身药|http://pigproxy.cn
左偏树的特点及其应用
广东省中山市第一中学黄源河

【摘要】
本文较详细地介绍了左偏树的特点以及它的各种操作。
第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。

【关键字】左偏树可并堆优先队列

【目录】
TOC\*MERGEFORMAT一、引言 PAGEREF_Toc93750614\h2
二、左偏树的定义和性质 PAGEREF_Toc93750615\h2
2.1优先队列，可并堆 PAGEREF_Toc93750616\h2
2.1.1优先队列的定义 PAGEREF_Toc93750617\h2
2.1.2可并堆的定义 PAGEREF_Toc93750618\h2
2.2左偏树的定义 PAGEREF_Toc93750619\h3
2.3左偏树的性质 PAGEREF_Toc93750620\h4
三、左偏树的操作 PAGEREF_Toc93750621\h5
3.1左偏树的合并 PAGEREF_Toc93750622\h5
3.2插入新节点 PAGEREF_Toc93750623\h7
3.3删除最小节点 PAGEREF_Toc93750624\h8
3.4左偏树的构建 PAGEREF_Toc93750625\h8
3.5删除任意已知节点 PAGEREF_Toc93750626\h9
3.6小结 PAGEREF_Toc93750627\h12
四、左偏树的应用 PAGEREF_Toc93750628\h13
4.1例——数字序列（Baltic2004） PAGEREF_Toc93750629\h13
五、左偏树与各种可并堆的比较 PAGEREF_Toc93750630\h15
5.1左偏树的变种——斜堆 PAGEREF_Toc93750631\h15
5.2左偏树与二叉堆的比较 PAGEREF_Toc93750632\h16
5.3左偏树与其他可并堆的比较 PAGEREF_Toc93750633\h16
六、总结 PAGEREF_Toc93750634\h18
【正文】
一、引言
优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。

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

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

2.1.2可并堆的定义
可并堆(MergeableHeap)也是一种抽象数据类型，