heapsort

Algorithm 232 heapsort. wikipedia: In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.[1]. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort. Heapsort was invented by J. W. J. Williams in 1964.[2] This was also the birth of the heap, presented already by Williams as a useful data structure in its own right.[3] In the same year, R. W. Floyd published an improved version that could sort an array in-place, continuing his earlier research into the treesort algorithm


References in zbMATH (referenced in 61 articles )

Showing results 1 to 20 of 61.
Sorted by year (citations)

1 2 3 4 next

  1. Lange, Kenneth: Algorithms from THE BOOK (2020)
  2. Volz, Marcus; Brazil, Marcus; Ras, Charl; Thomas, Doreen: Computing skeletons for rectilinearly convex obstacles in the rectilinear plane (2020)
  3. Erkan, Ö. Feyza; Cihan, Onur; Akar, Mehmet: Analysis of distributed consensus protocols with multi-equilibria under time-delays (2018)
  4. Gamby, Ask Neve; Katajainen, Jyrki: Convex-hull algorithms: implementation, testing, and experimentation (2018)
  5. Sevcik, Carlos: Fractal analysis of pi normality (2018)
  6. Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki: Optimizing binary heaps (2017)
  7. Gould, Nicholas I. M.; Robinson, Daniel P.: A dual gradient-projection method for large-scale strictly convex quadratic problems (2017)
  8. Lee, Chia-Wei; Chen, Pin-Liang; Hsieh, Sun-Yuan: Weight-constrained and density-constrained paths in a tree: enumerating, counting, and (k)-maximum density paths (2015)
  9. Kim, Jinha; Han, Wook-Shin; Oh, Jinoh; Kim, Sungchul; Yu, Hwanjo: Processing time-dependent shortest path queries without pre-computed speed information on road networks (2014)
  10. Brodal, Gerth Stølting: A survey on priority queues (2013)
  11. Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki: Weak heaps engineered (2013)
  12. Klein, Shmuel T.: On the connection between Hamming codes, Heapsort and other methods (2013)
  13. Browne, P. A.; Budd, C.; Gould, N. I. M.; Kim, H. A.; Scott, J. A.: A fast method for binary programming using first-order derivatives, with application to topology optimization with buckling constraints (2012)
  14. Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki: The weak-heap data structure: variants and applications (2012)
  15. Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki: Two skew-binary numeral systems and one application (2012)
  16. Letchford, Adam N.; Miller, Sebastian J.: Fast bounding procedures for large instances of the simple plant location problem (2012)
  17. Blunck, Henrik; Vahrenhold, Jan: In-place algorithms for computing (Layers of) maxima (2010)
  18. Geffert, Viliam; Gajdoš, Jozef: Multiway in-place merging (2010)
  19. Kaparis, Konstantinos; Letchford, Adam N.: Separation algorithms for 0-1 knapsack polytopes (2010)
  20. Navarro, Gonzalo; Paredes, Rodrigo: On sorting, heaps, and minimum spanning trees (2010)

1 2 3 4 next