Elementary average case analysis of Floyd''s algorithms to construct heaps
Tomi A. Pasanen · 1996
We reanalyse the average number of comparisons and assignments made during a heap construction by two Floyd''s algorithms: the original siftup algorithm and its more efficient version. These figures are derived from the average number of comparisons and assignments made on the path from the root of the heap to the final place of the root element, i.e., during one execution of the algorithms. We have two objectives in the analysis: First, we show that the analysis can be done with elementary calculations, involving only simple recursions and sums, being therefore accessible to wider audience. Second, these techniques give precise answers which are slightly stronger than the existing ones.