Skip to main content
SpringerLink
Log in

Weak-heap sort

  • Part I Computer Science
  • Published:
BIT Numerical Mathematics Aims and scope Submit manuscript

Abstract

A data structure called aweak-heap is defined by relaxing the requirements for a heap. The structure can be implemented on a 1-dimensional array with one extra bit per data item and can be initialized withn items using exactlyn−1 data element compares. Theoretical analysis and empirical results indicate that it is a competitive structure for sorting. The worst case number of data element comparisons is strictly less than (n−1) logn+0.086013n and the expected number is conjectured to be approximately (n−0.5)logn−0.413n.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Carlsson,Average-case results on heapsort, BIT, 27, 1987, pp. 2–17.

    Google Scholar 

  2. S. Carlsson, J. I. Munro and P. V. Poblete,An implicit binomial queue with constant insertion time, Proceedings of 1st Scandinavian Workshop on Algorithm Theory, Halmstad, Sweden, July 5–8, 1988, pp. 1–13.

  3. R. D. Dutton,The weak-heap data structure, Department of Computer Science Technical Report, CS-TR-92-09, 1992, University of Central Florida, Orlando, FL 32816.

    Google Scholar 

  4. R. W. Floyd,Algorithm 245,treesort 3, Comm. ACM, 1964, p. 701.

  5. C. A. R. Hoare,Algorithm 63, 64and 65, Comm. ACM, 4 (7), 1961, pp. 321–322.

    Google Scholar 

  6. C. J. H. McDiarmid and B. A. Reed,Building heaps fast, J. of Algorithms, 10, 1989, pp. 352–365.

    Google Scholar 

  7. J. R. Sack and T. Strothotte,An algorithm for merging heaps, Acta Informatica 22, 1985, pp. 171–186.

    Google Scholar 

  8. J. Vuillemin,A data structure for manipulating priority queues, Comm. of the ACM, 21 (4), 1978, pp. 309–315.

    Google Scholar 

  9. I. Wegener,Bottom-up heap sort, a new variant of heap sort beating on average quicksort (if n is not very small), Proceedings of Mathematical Foundations of Computer Science 1990, Banska Bystrica, Czechoslovakia, August, 1990, pp. 516–522.

  10. I. Wegener,The worst case complexity of McDiarmid and Reed's variant of Bottom-Up heapsort is less than n logn+1.1n, Information and Computation, 97, 1992, pp. 86–96.

    Google Scholar 

  11. J. W. J. Williams,Algorithm 232,Heapsort, Comm. of the ACM, 7, 1964, pp. 347–348.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, University of Central Florida, 32816, Orlando, FL, USA

    Ronald D. Dutton

Authors
  1. Ronald D. Dutton
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dutton, R.D. Weak-heap sort. BIT 33, 372–381 (1993). https://doi.org/10.1007/BF01990520

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01990520

CR Categories

Keywords

Search

Navigation