On the Number of Heaps and the Cost of Heap Construction
Hsien‐Kuei Hwang, Steyaert Jean-Marc · Birkhäuser Basel eBooks · 2002
Heaps constitute a well-known data structure allowing the implementation of an efficient O(n log n) sorting algorithm as well as the design of fast priority queues. Although heaps have been known for long, their combinatorial properties are still partially worked out: exact summation formulae have been stated, but most of the asymptotic behaviors are still unknown. In this paper, we present a number of general (not restricting to special subsequences) asymptotic results that give insight on the difficulties encountered in the asymptotic study of the number of heaps of a given size and of the cost of heap construction. In particular, we exhibit the influence of arithmetic functions in the apparently chaotic behavior of these quantities and study their extremal and average properties. It is also shown that the distribution function of the cost of heap construction using Floyd’s algorithm and other variants is asymptotically normal. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.