基于生成函数的二项树堆枚举计数公式推导

摘要：

通过对二项堆性质的深入研究,证明最大值堆的枚举计数递推公式适用于二项树堆(遵循堆性质的二项树).由二项树堆的枚举计数递推公式计算出的枚举数目能组成枚举值数列.把枚举值数列表示成生成函数,并根据生成函数的求和、微分、积分等运算将枚举值数列的生成函数化简为幂级数形式,进而对二项树堆的枚举计数递推公式进行化简,得到二项树堆的枚举计数公式.据此可直接计算出二项树堆的枚举总数目.经过实验验证,与递推计算二项树堆枚举总数目的方法相比,该方法的计算效率更高.

关键词：二项树堆、枚举计数、递推公式、生成函数、化简

所属期刊栏目：43

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2017-08-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：287-291