左偏树的特点与其应用.PDFVIP

左偏树的特点及其应用 左偏树的特点及其应用 广东省中山市第一中学 黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部 分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作 ，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学 竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特 点以及应用前景。 【关键字】左偏树 可并堆 优先队列 【目录】 一、引言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 【正文】 一、引言 优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和 贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用 的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合 ，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类 问题。 二、左偏树的定义和性质 在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。 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 ,H ) 1 2 Merge( ) 构造并返回一个包含H 和H 所有元素的新堆H 。 1 2 前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜 合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算 法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆 的比较。 2.2 左偏树的定义 左偏树(Leftist Tree)是一种可并堆的实现。左偏树是一棵二叉树，它的节点除了和二叉树的节 点一样具有