一种枚举生成所有最小-最大堆的算法

摘要

提出一种生成所有最小-最大堆的枚举算法.该算法采用单个数判断法和层次判断法,按照从深层次向低层次的顺序生成最小-最大堆;利用满堆的对称性,通过互换满堆的左右子树得到另外的最小-最大堆,从而减少回溯次数,有效提高枚举效率.%An enumeration algorithm of generating all the min-max heaps is put forward.It generates min-max heap in the order from deep level to low level with single number judgement method and level judgement method.Besides,the algorithm uses the symmetry of perfect heap to generate other min-max heap through crossing over the right and left sub-trees of the perfect heap,thus the backtracking times is reduced,and the enumeration efficiency is effectively improved as well.