Heapsort
Efficient comparison-based sorting using a binary heap.
Last updated
Heapsort is a comparison-based sorting algorithm that reorganizes an array into a heap and then repeatedly extracts the largest element.[1] It was invented by J. W. J. Williams in 1964, and Robert W. Floyd published an improved in-place version the same year.[2]
Key facts and history
Floyd's improvement built on his earlier research into the treesort algorithm.[2] A 2008 re-evaluation found bottom-up heapsort no faster than top-down heapsort for integer keys, due to modern branch prediction.[3] Its small implementation and dependable performance also make it popular in embedded systems.[4] J. W. J. Williams invented heapsort in 1964, and that same publication described the binary heap as a data structure.[2]
What the research sources say
The pdqsort algorithm uses heapsort as a fallback if too many bad partitions are encountered, switching after more than log(n) bad partitions.[5] On modern systems, heapsort is profiled to be approximately 1.8 to 2 times as slow as quicksort.[5] Empirical studies show that generally quicksort is considerably faster than heapsort.[6]
References
- Wikipedia, "Heapsort" (CC BY-SA 4.0), which cites: Cormen, "Introduction to algorithms", The MIT Press, 2022, p. 170 (we also read that source) en.wikipedia.org
- Wikipedia, "Heapsort" (CC BY-SA 4.0), which cites: ; Brass, "Advanced Data Structures", Cambridge University Press, 2008, p. 209; Brass, "Advanced Data Structures", Cambridge University Press, 2008, p. 209 (we also read that source) en.wikipedia.org
- Wikipedia, "Heapsort" (CC BY-SA 4.0), which cites: Mehlhorn, "Algorithms and Data Structures: The Basic Toolbox", Springer, 2008, p. 142 (we also read that source) en.wikipedia.org
- Wikipedia, "Heapsort" (CC BY-SA 4.0), which cites: Morris, "Comparing Quick and Heap Sorts", Data Structures and Algorithms, 1998; https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/sort.c#n205 Linux kernel source (we also read that source) en.wikipedia.org
- Peters, "pdqsort", Github, 9 Jun 2021. facts only, no text reused. github.com
- Morris, "Comparing Quick and Heap Sorts", Data Structures and Algorithms, 1998. facts only, no text reused. cs.auckland.ac.nz
Each numbered sentence above was checked against the source it cites before publication. Sentences citing Wikipedia adapt text from the English Wikipedia article Heapsort (contributors), used under CC BY-SA 4.0; this entry is available under the same licence. Other sources were used for facts only; no text or images are copied from them.
More in Algorithms And Data Structures
Sources
Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.
- Wikipedia: Heapsort (CC BY-SA 4.0).
- Word definitions: the Codexery glossary, each quoted from its Wikipedia article.
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced