Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering

Previous Articles     Next Articles

Enumeration Counting Formula Derivation of Binomial Tree Heap Based on Generating Function

LI Chao  1,SUN Qiang  1,ZHANG Zhujun  2   

  1. (1.Department of Computer Science and Technology,East China Normal University,Shanghai 200241,China; 2.Water Resource Administrative Institute of Fengxian District of Shanghai,Shanghai 201400,China)
  • Received:2016-01-05 Online:2017-01-15 Published:2017-01-13

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

李超 1,孙强 1,张诸俊 2   

  1. (1.华东师范大学 计算机科学技术系,上海 200241; 2.上海市奉贤区水资源管理所,上海 201400)
  • 作者简介:李超(1989—),男,硕士研究生,主研方向为数据结构与算法分析;孙强,副教授;张诸俊,助理工程师。

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

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

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

CLC Number: