作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (20): 64-65. doi: 10.3969/j.issn.1000-3428.2010.20.022

• 软件技术与数据库 • 上一篇    下一篇

左倾堆枚举计数递推公式及实现

李言刚,孙 强   

  1. (华东师范大学计算机科学与技术系,上海 200241)
  • 出版日期:2010-10-20 发布日期:2010-10-18
  • 作者简介:李言刚(1983-),男,硕士研究生,主研方向:数据结构;孙 强,副教授

Recursive Formula for Leftist Heap Enumeration Counting and Its Implementation

LI Yan-gang, SUN Qiang   

  1. (Dept. of Computer Science and Technology, East China Normal University, Shanghai 200241, China)
  • Online:2010-10-20 Published:2010-10-18

摘要: 通过对左倾堆性质和定理的深入研究,用组合的方法推导出含n个不同节点的左倾堆的枚举计数的递推公式,并用程序进行实现和验证,给出相应的实验结果,从而为非完全二叉树型的堆结构的枚举计数提供借鉴和参考,同时也为左倾堆枚举生成和随机生成以及左倾堆的平均算法复杂性的分析奠定基础。

关键词: 左倾堆, 枚举, 计数, 组合, 递推公式

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

中图分类号: