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

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

Abstract: This paper proves that the enumeration counting recursion formula of max-heap is appliable to binomial tree heap(binomial tree that obeys the heap property) based on intensive study of the property of binomial heap.The enumeration number of binomial tree heap calculated from the enumeration counting recursion formula of binomial tree heap can make up an enumeration series.Then,the enumeration series is expressed as a generating function which is simplified into a power series based on adding,differentiating,integrating,and other operation of the generating function,thus,simplifying the enumeration counting recursion formula of binomial tree heap thoroughly and obtaining the enumeration counting formula of binomial tree heap.According to this result,the enumeration number of binomial tree heap can be calculated directly.Experiment proves that the direct calculation method has a higher calculation efficiency than the recursive method.

Key words: binomial tree heap, enumeration counting, recursive formula, generating function, simplification

中图分类号: 

• TP301.6