Algorithm Of Enumrating Max-heaps Based On Subtree Generating

Binary tree is one of the most fundamental and important data structure used in computer science. Thus, the problem of enumerating binary trees is of great interest both theoretically and practically.In this paper, four categories of coding algorithms for generating binary trees were introduced first.Heap is an important binary tree structure which has often been used in the applications concerned with Priority Queues, Sorting, Shortest Paths, Task Schedule, and Minimum Spanning Tree. Therefore, enumerating heaps will be helpful in the areas mentioned above. Enumerating heaps has two meanings. One is counting, which is determining the number of some kind of trees; And the other is generating, which means listing all the heaps having some kind of property one by one.Afterward, surveys of different kinds of heap structures were made. We introduced a recently discovered property of Max-heaps and an algorithm of generating Max-heaps based on this property[5].At the end of this paper, the problem of enumerating Max-heaps was studied and an algorithm was put forward, which based on subtree generating for enumerating Max-heaps. This algorithm divides the process of enumerating heap into select the root, enumerating left-subheap and enumerating right-subheap; then combines the root,left-subheap,and right-subheap to make a whole heap. It turns enumerating one k layers heap to enumerating two k-1 layers heap, thus this algorithm can increase the efficiency of enumerating.In addition, the process of enumerating can be divided recursively. This recursive algorithm has higher efficiency and can be implemented without recursion.We can learn the increase of efficiency through comparion between the algorithms put forword in this paper and the algorithm in the literature[5].