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.
श्रेणियाँ:
साल:
1985
संस्करण:
Dissertation
भाषा:
english
पृष्ठ:
75
फ़ाइल:
DJVU, 469 KB
IPFS:
,
english, 1985