Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
Heapsort is a sorting algorithm that has a time complexity of O(nlogn), and performs sorting using O(1) space complexity. However, I know that because it's unstable, it doesn't find many applications (f.e. compared to other sorting algorithms).
I know it's used for interval scheduling.
What are some practical applications of heapsort?
EDIT: As @AProgrammer pointed out, quick sort isn't stable either.
Quicksort isn't stable. Quicksort has a lower constant factor than heap sort, but it's worst case complexity is O(N^2), so some variant switch back to heapsort in order to avoid that behavior (for instance introsort, but I'm pretty sure I've seen the idea applied in the early 90's).
Heapsort is great when you need to know just the "smallest" (or "largest") of a collection of items, without the overhead of keeping the remaining items in sorted order. For example, a PriorityQueue.
Heap sort is always O(nlogn) without the Quicksort worst case of O(n2). This is important in order to put an upper bound on the maximum processing time.
Heapsort is also useful in some applications because processing can begin before all the data is available. Data could be received in packets with time delays. Rather than wait for all the data to arrive before starting to sort, Heapsort can begin with the first element to arrive and proceed incrementally so that its nearly complete when the last element is available.
Quicksort does not behave well on small inputs, because there is a big chance that the pivot will be chosen badly (not a median of all sorted elements). Hence, Heapsort or even Insertion sort is usually used for sized arrays.
From here stems another application of heapsort - Intosort. Introsort is a sorting algorithm, which combines strengths of both quicksort and heapsort. Large arrays are sorted using quicksort, but when expected limit of depth is reached - log2n - the algorithm swaps to heapsort.
I would say that if the complexity O(nlog2n) is not needed to be guaranteed, than quicksort is (almost) always used, bacause it is on average faster and is a widely used library algorithm. If you want to improve the behaviour of Quicksort, than you use it in conjuction with Heapsort. And only when the O(nlog2n) is to be guaranteed, than the implementations use plain heapsort.
