计算机工程2017，Vol.43Issue(1)：287-291,5.DOI:10.3969/j.issn.1000-3428.2017.01.049
基于生成函数的二项树堆枚举计数公式推导
Enumeration Counting Formula Derivation of Binomial Tree Heap Based on Generating Function
李超 1孙强 1张诸俊2
作者信息
- 1. 华东师范大学计算机科学技术系,上海200241
- 2. 上海市奉贤区水资源管理所,上海201400
- 折叠
摘要
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分类
信息技术与安全科学引用本文复制引用
李超,孙强,张诸俊..基于生成函数的二项树堆枚举计数公式推导[J].计算机工程,2017,43(1):287-291,5.
