cp's OEIS Frontend

There are two places in R. W. Floyd's modified algorithm where the keys are compared. The first is in step H4 [Find larger child.] and the second in step H9' [Does K fit?]. The sequence is the sum of the counts of these comparisons, taken over all n! possible orders of the records.

The following table shows the maximum and average number of key comparisons for the original algorithm and for its modified version.

Algorithm H Modified algorithm

.

n Worst case Worst case

| A350426(n) A350427(n)

| | Average | Average

| | 2*A350428(n)/n! | A350569(n)/n!

| | | Average/ | | Average/

| | | (n*log(n)) | | (n*log(n))

2 1 1.000 0.721 1 1.000 0.721

3 3 3.000 0.910 3 3.000 0.910

4 7 6.500 1.172 7 6.417 1.157

5 12 10.950 1.361 12 10.475 1.302

6 17 15.133 1.408 16 14.100 1.312

7 22 19.789 1.453 20 18.166 1.334

8 29 25.814 1.552 27 22.876 1.375

9 37 32.524 1.645 34 28.347 1.433

10 44 38.631 1.678 39 32.871 1.428

11 51 45.237 1.715 44 38.020 1.441

12 59 51.845 1.739 51 43.048 1.444

13 66 59.021 1.770 57 48.737 1.462

14 73 65.488 1.773 63 53.479 1.447

This is compatible with Don Knuth's remark, quoted from TAOCP Vol. 3, page 148: Heapsort has the interesting property that its worst case isn't much worse than the average.

There are two places in the algorithm where the keys are compared. The first is in step H4 [Find larger child.] and the second in step H6 [Larger than K?]. The sequence is the sum, divided by 2, of the counts of these comparisons, taken over all n! possible orders of the records.

There are two places in R. W. Floyd's modified algorithm where the keys are compared. The first is in step H4 [Find larger child.] and the second in step H9' [Does K fit?]. The sequence shows the maxima of the counts of these comparisons, determined over all n! possible orders of the records.