论文部分内容阅读
堆是最基本的数据结构之一,对堆进行枚举,可以作为堆上算法复杂性分析的有力工具,有着重要的意义。堆的枚举有两种含义,一种是计数,即计算出具有某种特性的堆的总数目;另一种是生成,即一个一个地产生所有的具体堆。最小一最大堆是一种完全二叉树形状的堆结构,现已被广泛应用在数据排序、最短路求解、任务调度、最小生成树等诸多领域。在最小一最大堆上以D(1)的复杂度即可取得最小元与最大元;插入元素、删除最小元、删除最大元的复杂度都是<=)(10g")。对这些运算的高效支持使得最小一最大堆成为双端优先队列的优秀实现方法。由于其完全二叉树形状的特点,可以使用操作简便的隐式存储结构进行存储,避免了复杂的指针操作,它从而得到广泛应用。首先,在已有计数公式的基础上,结合对堆中各子树结点数的研究,本文得出了含,z结点的堆的直接计数公式。不同于以往基于递推的计数公式,本文公式仅与结点数,l有关,是一个直观的计数公式,由它得到的求解算法时间复杂度是D(,z);较之已有的计数算法,此计数算法避免了以往《二)(,z)的存储空间。接着,本文先给出了一个基础的最小一最大堆生成算法LBG,它采用了“单个数判断法”和“层次判断法”两个基本方法以减少冗余步骤的生成。该基础算法可以完备地枚举出所有含,z个结点的最小一最大堆。最后,考虑到满堆在枚举集合上具有对偶特性,在进行堆的生成时,可以仅生成每对对偶堆中的一个,通过交换根结点的左右子树得到另一个堆;另外,将一个最小一最大堆的生成分解成对其两个子堆的生成,即:一个满堆和一个完全子堆的生成,本文提出了改进的生成算法DBG。通过将堆进行分解,实现了把七层堆的生成转换成对两个k-1层堆的生成,对满堆的生成利用了对偶性,大幅度减少了生成堆所花费的时间,提高了算法的效率。实验表明,与基础算法LBG相比,算法DBG的生成时间开销平均提高了87%。以上这些工作为进一步研究最小一最大堆提供了有力的帮助。