Abstract:
A recursive formula of enumeration number of leftist heap with n different nodes is put forward using the combination method based on the definition, facts and theorems of leftist heap. An algorithm on this formula is also given in this paper and is verified by a program. The work of this paper can provide some reference for n binary tree enumeration that is not a complete tree as well as can provide a foundation for leftist heap’s enumeration generating, random generating and average complexity analysis.
Key words:
leftist heap,
enumeration,
counting,
combination,
recursive formula
摘要: 通过对左倾堆性质和定理的深入研究,用组合的方法推导出含n个不同节点的左倾堆的枚举计数的递推公式,并用程序进行实现和验证,给出相应的实验结果,从而为非完全二叉树型的堆结构的枚举计数提供借鉴和参考,同时也为左倾堆枚举生成和随机生成以及左倾堆的平均算法复杂性的分析奠定基础。
关键词:
左倾堆,
枚举,
计数,
组合,
递推公式
CLC Number:
LI Yan-Gang, SUN Jiang. Recursive Formula for Leftist Heap Enumeration Counting and Its Implementation[J]. Computer Engineering, 2010, 36(20): 64-65.
李言刚, 孙强. 左倾堆枚举计数递推公式及实现[J]. 计算机工程, 2010, 36(20): 64-65.