Combinatorial properties of heapsort

Al-Jaber Ah.

Several aspects related to the combinatorial properties of heapsort are discussed in this thesis. A recursion formula for the number of heaps satisfying a given condition between any two offsprings with the same parent Is given and several properties of heaps are discussed Including a new algorithm to generate the set of all heaps of any size. Also In this work we define second order trees which have a great Importance In the study of the complexity of Williams’ algorithms to generate a heap. We discuss this kind of trees and we prove that the generating function of the number of trees satisfies a nonlinear differential difference equation. The numerical computation and the asymptotic expansion for a quantity related to this nonlinear differential difference equation Is given In this work . Finally, we give an upper bound for the number of the second order trees generated from the set of all heaps of size N where N has the form 2-1 for any positive integer k.