Research On Enumeration Number And Generation Algorithm Of Binomial Tree Heap

Enumeration of trees includes the generation and counting. Researches on the enumeration of trees play an important role in many fields of computer, especially in the field of algorithm analysis.Binomial Heap is one of the best data structures to implement the priority queue and process scheduling algorithm. This paper defines Binomial Tree Heap, which is consistent with the nature of the heap of binomial trees (Binomial Tree is a class of ordered trees). The binomial heap is composed of a set of binomial tree heap in accordance with the rules. Thus, researches on the binomial tree heap counting and enumeration algorithm are the basis of researches on the enumeration of the binomial heap. The enumeration value of the tree can form series and the generating function is a powerful tool for processing sequence and recursion. In this paper, we focus on the method to derive the binomial tree heap enumeration formula with the generating function, and also design and implement the binomial tree heap enumeration generation algorithm.First, this paper proposed two methods to derive binomial tree heap enumeration counting formula with generating function. One method is to derive the binomial tree heap enumeration number of recursive formula by analyzing the characteristics of binomial tree heap structure. Then the recursive formula is simplified by the generating function. The second method is directly to process binomial tree heap enumeration value recursion formula, which is on the basis of the first method and combined with the mathematical combination method. Compared to the first method, the second method is more simple and straightforward. In this paper, a practical algorithm of calculating the binomial tree heap enumeration number whose time complexity is O(n) is also designed and its performance on calculation is also proved and verified through experiment.Then this paper designs and implements two binomial tree heap enumeration algorithm:generation algorithm based on combination and recursion (CRBG) and generation algorithm based on judgement of hierarchy (JHBG). CRBG algorithm transforms the generation of binomial tree heap into the generation of more sub binomial tree heap, ultimately combines the generated sub binomial tree heaps into a binomial tree heap. In JHBG algorithm, the Max-heap’s level judgment method is applied to generate binomial tree heap.Finally, experiments validate the correctness and avaliabilty of the two algorithms. Through experimental verification, we can draw a conclusion that this paper proposed CRBG algorithm and JHBG algorithm insignificantly improved the generation efficiency compared with the previous generation algorithm based on permutation (PBG) with increasing by 41% and 53%, respectively.