# Applications of heapsort [closed]

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.

• Well, using O(1) is pretty nice, especially in embedded or otherwise restricted systems. Imagine you need to sort a huge list but have very limited memory. And stability is a nice feature for a sorting algorithm, but certainly not always required. Apr 8, 2013 at 10:20
• Intro sort (en.wikipedia.org/wiki/Introsort) is an efficient implementation of quick sort that falls back to heap sort if the recursion levels grows beyond a certain threshold (the logarithm of the size of the input data). Without this kind of measures, quick sort has worst case time complexity O(n^2). Apr 8, 2013 at 11:13
• There is an anecdote (that isn't a good answer) I recall reading about manually sorting a large set of data in bootcamp which was simplified using heapsort. Visit chat, ask, and I'll relate the story that I recall there.
– user40980
Apr 18, 2013 at 17:34

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).

• +1: I have run some experiments some time ago and a naive implementation of quick sort can easily hit some "bad data" and perform much worse than merge sort or heap sort. Intro sort does not suffer from this problem and combines advantages of both algorithms (quick sort and intro sort). Apr 8, 2013 at 11:21

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.

• +1 Very good! I programmed a HeapSort using built-in array type in Java during a Data Structures course. Apr 8, 2013 at 14:34
• Um, isn't this just the heap data structure, not the sorting algorithm based on and named after said data structure?
– user7043
Apr 8, 2013 at 16:00
• If you only need to find the smallest and the largest elements, you don't need to sort the data at all. You can find both in one pass over the data. Apr 8, 2018 at 16:53

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.