Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program

Article type: Research Article

Authors: Suchenek, Marek A.

Affiliations: Department of Computer Science, California State University Dominguez Hills, Suchenek@csudh.edu

Note: [] Address for correspondence: Marek A. Suchenek, California State University Dominguez Hills, Department of Computer Science, 1000 E. Victoria St., Carson, CA 90747, USA I would like to express my utmost gratitude to a number of individuals for their kindness and invaluable help in turning various drafts of this paper into a journal publication. These were: Victor W. Marek, Philip Wadler, Greg Morrisett, Damian Niwiński, Ken Leyba, an Anonymous Referee of POPL'12, and - last but not least - the Editorial Board and the Anonymous Referee of the Fundamenta Informaticae. Northrop Grumman Information Systems (a division of Northrop Grumman Corporation)'s continuous support of my department provided me with teaching release time some of which I used for writing this paper.

Abstract: The worst-case behavior of the heap-construction phase of Heapsort escaped mathematically precise characterization by a closed-form formula for almost five decades. This paper offers a proof that the exact number of comparisons of keys performed in the worst case during construction of a heap of size N is: 2N − 2s2(N) − e2(N), where s2(N) is the sum of all digits of the binary representation of N and e2(N) is the exponent of 2 in the prime factorization of N. It allows for derivation of this best-known upper bound on the number of comparisons of Heapsort: (2N − 1)$\lceil$lgN$\rceil$ − 2$\lceil$lgN$\rceil$+1 − 2s2(N) − e2(N) + 5.

Keywords: Heapsort, worst-case analysis, sum of digits

DOI: 10.3233/FI-2012-751

Journal: Fundamenta Informaticae, vol. 120, no. 1, pp. 75-92, 2012