左倾堆枚举算法的研究

摘要

枚举有两层含义：一是计数，即计算具有某种特性的所有对象的个数；二是生成，即产生具有某特性的所有对象。本文主要介绍了二叉树的枚举，最大值堆的枚举和自己所研究的左倾堆的枚举。
　　 二叉树是一种重要的数据结构。二叉树枚举的研究无论在算法理论上还是在实际应用中都具有重要的意义。与二叉树枚举计数相关的最有名的就是Catalan数。目前二叉树的枚举生成主要是基于编码的二叉树生成算法[3-8]，这些算法建立了二叉树集合和编码集合间的一一对应关系，将二叉树的枚举生成问题转化为编码的枚举生成问题。
　　 最大值堆在结构上是一棵完全二叉树。最大值堆的枚举生成是将数值映射到结构固定的完全二叉树上。目前最大值堆的枚举生成[10-14]大都是基于回溯法，并采用单个数判断法和层次判断法来减少回溯的次数。
　　 左倾堆是具有堆序性质和左倾性质的特殊二叉堆。它可以作为优先队列的一种实现方式，跟普通的二叉堆相比，有着更加高效的合并操作[16]。左倾堆的枚举对于研究左倾堆的性质、分析其相关算法的平均复杂性有着重要意义，并为左倾堆的随机生成提供了基础。本文首先根据左倾堆的距离和结点数的关系，用组合方法推导出了左倾堆枚举计数的递推公式，然后提出了基于构造的左倾堆枚举生成算法和基于排列的左倾堆枚举生成算法。基于构造的左倾堆的枚举生成算法是在含n-1个结点的左倾堆中插入一个结点构造所有含n个结点的左倾堆；基于排列的左倾堆枚举生成算法的依据是本文提出的一个定理，即一个二叉堆的中序序列能够唯一的确定该二叉堆。该定理确立了一个含n个结点的二叉堆与一个n元排列的一一对应关系。基于排列的左倾堆枚举生成算法通过生成n元排列，将排列看成是二叉堆的中序序列，通过中序序列来构造二叉堆，再从二叉堆中筛选出左倾堆，该算法简化了左倾堆的枚举过程，相对比基于构造的左倾堆的枚举生成算法，左倾堆的枚举生成效率提高了35％以上。同时本文进一步改进了基于排列的左倾堆枚举生成算法，使得左倾堆的枚举生成效率进一步提高了40％左右。
　　 本文最后对三种结构的枚举进行了总结，对左倾堆枚举生成的进一步改进方法进行了讨论。

目录

文摘

英文文摘

声明

第一章 绪论

1.1 研究的背景和意义

1.2 本文的主要工作

1.3 本文的内容安排

第二章 二叉树的枚举

2.1 二叉树的相关概念和符号约定

2.2 二叉树的枚举计数

2.3 二叉树的排序

2.4 二叉树的排名和解析排名

2.5 二叉树的枚举生成算法

2.5.1 二叉树的编码过程

2.5.2 基于树排列的编码生成算法

第三章 最大值堆的枚举

3.1 堆的相关概念及符号约定

3.2 最大值堆的枚举计数

3.2.1 Kurz的递归计数公式

3.2.2 满堆的计数公式

3.2.3 求任意一个最大值堆的枚举总数的实用算法

3.2.4 最大值堆的枚举计数公式

3.3 最大值堆的枚举生成算法

3.3.1 最大值堆的一个层次性质

3.3.2 最大值堆的生成算法

第四章 左倾堆的枚举

4.1 左倾堆的相关概念和基本操作

4.1.1 左倾堆的基本概念

4.1.2 左倾堆的合并

4.2 左倾堆的枚举计数

4.2.1 左倾堆枚举计数递推公式

4.2.2 左倾堆枚举计数递推公式的实现描述

4.3 左倾堆的枚举生成

4.3.1 基于构造的左倾堆枚举生成算法

4.3.2 基于排列的左倾堆枚举生成算法

第五章 结束语

5.1 本文总结

5.2 展望

参考文献

攻读硕士学位期间发表的论文

致谢