Some observations on the average behavior of heapsort
- 1 October 1980
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 229-237
- https://doi.org/10.1109/sfcs.1980.38
Abstract
In this note some aspects of the average behavior of the well known sorting algorithm heapsort are investigated. 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 investigated.Keywords
This publication has 2 references indexed in Scilit:
- A hardware wrapper for the SHA-3 hash algorithmsPublished by Institution of Engineering and Technology (IET) ,2010
- Sequence of operations analysis for dynamic data structuresJournal of Algorithms, 1980