A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm

Abstract

In this paper a tight bound on the worst-case number of comparisons for Floyd's well known heap construction algorithm, is derived. It is shown that at most 2n-2μ(n)-σ(n) comparisons are executed in the worst case, where μ(n) is the number of ones and σ(n) is the number of zeros after the last one in the binary representation of the number of keys n.

arXiv commentThis (full) paper was accepted for publication in the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM2011), 22-28 January 2011, Novy Smokovec, Slovakia (9 pages)