Research On Enumeration Algorithm For Leftist Heap

There are two meanings of enumeration. One is counting, that is to count the number of the objects with some characteristics; the other is generating, that is to generate all the objects with these characteristics. This paper is mainly discussing the enumerations of binary trees, max heaps and leftist heaps. The enumeration of leftist heaps is the major part of my job.Binary tree is an important data structure. The enumeration of binary tree is of great interest from theoretical and practical point of view. The most famous result related to the counting of binary tree enumeration is Catalan number. Now, the algorithm of generating binary trees is mainly based on coding methods, which construct one to one correspondence between binary trees and coding. Meanwhile, they convert the generation of binary trees to the generation of coding.Max heap is structurally a complete binary tree. The generation of max heap is to put values to the structure of fixed complete binary tree. Presently, the generation of max heap is mostly based on backtracking, which uses single number judge and hierarchy judge to reduce backtracking times.Leftist heap is a special binary heap with heap order and leftist property. Firstly, this paper deduced the recursive formula of leftist heap enumeration number, secondly, it brings up two algorithms of generating all leftist heaps. One uses method of construction, the other is the algorithm based permutation. The first algorithm is generating all leftist heaps with n nodes by inserting one node to the leftist heaps with n-1 nodes. The second algorithm is according to the theorem that a heap's mid-order sequence can construct the binary heap uniquely, which builds one to one correspondence between a binary heap with n nodes and a permutation with n elements. The algorithm based on permutation generates a permutation with n elements and considers this permutation as a mid-order sequence and then uses this mid-order sequence construct the binary heap and judge whether the binary heap is a leftist heap. When all permutations with n elements generated, all the leftist heaps is generated. The second algorithm increases the efficiency by 35% comparing with the first one. Finally, the algorithm based on permutation is improved and the efficiency is raised by 40% farther.This article finally compares the three structures' enumeration and gets a summarization, making the prospect for improving method of generating leftist heaps.