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 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.
View the SourceFrequently Asked Questions
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.
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.