A comparison sort that first arranges the input into a heap and then repeatedly removes the largest element from the top of the heap, giving guaranteed worst-case log-linear time with no extra memory beyond the input array.
Facts
Time Complexity Credited ToJ. W. J. Williams (1964) 1 Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 FAQs
Why do real-world quicksort implementations often include heapsort as well?
Most practical quicksort implementations fall back to heapsort when they detect quicksort is becoming degenerate.
Most real-world quicksort variants include an implementation of heapsort as a fallback, one they switch to should they detect that quicksort is becoming degenerate. This pairing lets an implementation lean on quicksort's usual speed while still holding heapsort's dependable worst-case bound in reserve for the cases where quicksort itself would not perform well.
Connections
Sources
1. Wikipedia, Heapsort
Lead section
Heapsort was invented by J. W. J. Williams in 1964.
Williams' heap construction
Because it is dominated by the second heap-extraction phase, the heapsort algorithm itself has O(n log n) time complexity using either version of heapify.
- Wikipedia Heapsort infobox worst-time O(n log n)
View the SourceWikidata: Heapsort
Wikidata Q474095, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.