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

• Autorzy: Suchenek M. A.
• Języki publikacji: EN

Abstrakty

EN

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-2s_2(N) - e_2(N); where s_2(N) is the sum of all digits of the binary representation of N and e_2(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: [formula]

Słowa kluczowe

EN

heapsort; worst-case analysis; sum of digits

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 120, nr 1
• Strony: 75--92
• Opis fizyczny: Bibliogr. 9 poz., wykr.

Twórcy

autor

Suchenek M. A.

• California State University Dominguez Hills, Department of Computer Science, 1000 E. Victoria St., Carson, CA 90747, USA,

Bibliografia

• [1] SARA BAASE, Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley Publishing, 2nd ed., 1991.
• [2] THOMAS H. CORMEN, CHARLES E. LEISERSON, RONALD L. RIVEST, AND CLIFFORD STEIN, Introduction to Algorithms, MIT Press and McGraw-Hill, 3rd ed., 2009.
• [3] ROBERT W. FLOYD, Algorithm 245: Treesort 3., Communications of the A.C.M., 7 (1964), p. 701.
• [4] DONALD E. KNUTH, The Art of Computer Programming, vol. 3, Addison-Wesley Publishing, 2nd ed., 1997.
• [5] JOHANNES F. MORGENBESSER, Gelfonds sum of digits problems, Master's thesis, Technische Universität Wien, 2008. http://dmg.tuwien.ac.at/drmota/morgenbesserda.pdf.
• [6] IOANNIS K. PAPARRIZOS, A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm, in 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM2011), Novy Smokovec, Slovakia, 2011, pp. 22-28. arXiv:1012.0956v3 [cs.DS] 18 Apr 2011.
• [7] RUSSEL W. SCHAFFER, Analysis of Heapsort, PhD thesis, Princeton Univeristy, 1992.
• [8] JOHN W. J. WILLIAMS, Algorithm 232: Heapsort, Communications of the A.C.M., 7 (1964), pp. 347-348.
• [9] WWW Heapsort in Java at: http://csc.csudh.edu/suchenek/MakeHeap.html