A tight lower bound for the worst case of Bottom-Up-Heapsort | SpringerLink
Skip to main content
Springer Nature Link
Log in

A tight lower bound for the worst case of Bottom-Up-Heapsort

Extended Abstract

  • Conference paper
  • First Online:
ISA'91 Algorithms (ISA 1991)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 557))

Included in the following conference series:

Abstract

Bottom-Up-Heapsort is a variant of Heapsort. Its worst case complexity for the number of comparisons is known to be bounded from above by 3/2n log n+O(n), where n is the number of elements to be sorted. There is also an example of a heap which needs 5/2n log n−O(n log log n) comparisons. We show in this paper that the upper bound is asymptotical tight, i.e. we prove for large n the existence of heaps which need at least c n ·(2nlog n−O(n log log n)) comparisons where c n=1−log 2 n/1 converges to 1. This result also proves the old conjecture that the best case for classical Heapsort needs only asymptotical nlogn+O(n log log n) comparisons.

This work was supported by the ESPRIT II program of the EC under contract No. 3075 (project ALCOM)

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. S. Carlsson “A variant of HEAPSORT with almost optimal number of comparisons” Information Processing Letters 24 (1987), 247–250

    Google Scholar 

  2. S. Carlsson ”Average-case results on HEAPSORT” BIT 27 (1987), 2–17

    Google Scholar 

  3. R. Fleischer ”A tight lower bound for the worst case of bottom-up-heapsort” Technical Report MPI-I-91-104, Max-Planck-Institut für Informatik, W-6600 Saarbrücken, Germany, April 1991

    Google Scholar 

  4. R. Fleischer, B. Sinha, C. Uhrig ”A lower bound for the worst case of bottom-up-heapsort” Technical Report No. A23/90, University Saarbrücken, December 1990

    Google Scholar 

  5. C.J.H. McDiarmid, B.A. Reed ”Building heaps fast” Journal of Algorithms 10 (1989), 352–365

    Google Scholar 

  6. K. Mehlhorn ”Data Structures and Algorithms, Vol. 1, Sorting and Searching” Springer Verlag, Berlin, 1984

    Google Scholar 

  7. R. Schaffer, R. Sedgewick ”The analysis of heapsort” Technical Report CS-TR-330-91, Princeton University, January 1991

    Google Scholar 

  8. I. Wegener ”BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating on average QUICKSORT (if n is not very small)” MFCS'90, Lecture Notes in Computer Science, 516–522, 1990

    Google Scholar 

  9. I. Wegener ”The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP-HEAPSORT is less than n log n +1.1n” Proc. STACS 1991, 137–147

    Google Scholar 

  10. J.W.J. Williams ”Algorithm 232” Communications of the ACM 7 (1964), 347–348

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Saarland, D-6600, Saarbrücken, Germany

    Rudolf Fleischer

Authors
  1. Rudolf Fleischer
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Wen-Lian Hsu R. C. T. Lee

Rights and permissions

Reprints and permissions

Copyright information

© 1991 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fleischer, R. (1991). A tight lower bound for the worst case of Bottom-Up-Heapsort. In: Hsu, WL., Lee, R.C.T. (eds) ISA'91 Algorithms. ISA 1991. Lecture Notes in Computer Science, vol 557. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54945-5_69

Download citation

  • DOI: https://doi.org/10.1007/3-540-54945-5_69

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-54945-1

  • Online ISBN: 978-3-540-46600-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics