Research On Enumeration Algorithm For Min-Max 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 is to calculate the total number of heaps with special characteristics; the other one is generating, means, to generate specific heaps of particular features.Min-Max Heap, a heap-shaped complete binary tree, is now widely used in data sorting, shortest path solving, task scheduling, minimal spanning tree and many other related fields. We can search both minimum and maximum at O(1) on them. The Min-Max Heap supports operations such as Insert(), DeleteMin(), DeleteMax() in O(log n). These outstanding attributes of Min-Max Heap contribute to its being the simplest realization of Double Ended Priority Queue.Based on the existing counting methods, combined with analysis on the node number of sub trees, we concluded a new direct counting formula. This formula only related to the number of nodes as n, we can generate a O(n) algorithm to realize it. Compared with the former solution, we don't need the O(n) extra storage space.Then, this paper gave an ordinary algorithm LBG to enumerate all Min-Max Heaps. Single Number and Level Judgment were adopted to decrease redundant process. LBG can completely generate all the Min-Max Heaps with n nodes.Finally, considering the enumeration set of the perfect heap has duality, during the generation of the heap, we can generate one heap of each dual pair, and get another one through the exchange of left and right sub-tree of dual node; we divided the whole generating process into two parts: the sub processes of a complete sub-heap and a perfect sub-heap. Then, we designed DBG. By decomposing the whole heap, we realized to convert the generating of k level heap into two k-1 level generation. With the application of duality on perfect heaps, we effectively reduced the time it cost, then, greatly improved the efficiency. Compared with the basic generating algorithm LBG, we enhanced by 87% in the cost of enumerating time with DBG.