Research On Enumeration Generation Algorithms For Heap

Heap is one kind of the basic data structures. Enumeration study on heaps can be used as a powerful tool to help algorithm complexity analysis, which implies important significance. There are two meanings of enumerating heaps. one is counting, which id to calculate the total number of heaps with special characteristics; the other one is generating, means, to generate specific heaps of particular features. Heap is a kind of important binary tree, mainly used in data sorting, priority queues, the most short circuit solve, minimum spanning tree and some network optimization problems.The paper researches the existing enumeration algorithm. And it analyzes the time complexity and space complexity about different algorithm, including binary tree,maximum heap and leftist heap. According to different heap enumeration, it mainly complete the following work:Combined with the research about the number of the sub-tree nodes and the heap structure, to improve the space complexity about the heap enumeration generation algorithm, the paper first raises a "based on the arrangement" about the maximum heap enumeration generation algorithm. It gives the number, by the permutation algorithm, generates all the permutations to judge which can be the in order sequence of the maximum heap, and then generates the maximum heap. Accounting the recursive nature of the maximum heap structure, the paper determines the process recursive. That is, to the maximum value in the arrangement as a dividing point, recursive judge left permutation (left of the maximum) and the right permutation (right of the maximum), if it able to the left sub-tree and the right sub-tree. Judgment recursive process sucked already Permutation divided into more and smaller permutation to determine. Comparing to the previous maximum heap generation algorithm, this algorithm saves O(n) space about the stack.Secondly, based on the "single number judgment method" and the "level judgment method", the article put forward a "bottom to high" generation algorithm. It first generates the bottom node, last generates the first level. It has provided a reliable method in the process of the bottom point application. Compared to "based on permutation" enumeration algorithm, it increase a O(n) storage space. But because of the "level judgment method", this algorithm reduces the redundant steps of generating. Experimental result show that, compared to the "based on permutation" enumeration algorithm, the algorithm generates time decreases by an average of80%.Finally, the paper summarizes all heap enumeration algorithms, and put forward a improved method and prospect. These works provide a powerful help for the further research about heap, also laid the foundation for further research.