SOME OBSERVATIONS ON THE AVERAGE BEHAVIOR OF HEAPSORT (Preliminary Report)
Ernst–Erich Doberkat · Foundations of Computer Science · 1980
In this note some aspects of the average behavior of the well known sorting algorithm heapsort are investi gated. There are two different methods to construct heaps, which are due to Williams, and to Floyd, and for both methods the respective distribution of the heaps is computed in a continuous model. For Floyd's method moreover the expected number of interchanges, and comparisons which are necessary to construct a heap are derived. For the selection phases of both algorithms the respective distributions are investi gated.