Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Joachim Sauer Apr 8 '13 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). –  Giorgio Apr 8 '13 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. –  MichaelT Apr 18 '13 at 17:34

4 Answers 4

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.

share|improve this answer
    
+1 Very good! I programmed a HeapSort using built-in array type in Java during a Data Structures course. –  Mushy Apr 8 '13 at 14:34
4  
Um, isn't this just the heap data structure, not the sorting algorithm based on and named after said data structure? –  delnan Apr 8 '13 at 16:00

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

share|improve this answer
    
+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). –  Giorgio Apr 8 '13 at 11:21

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 heapsort, but when expected limit of depth is reached - log2n - the algorithm swaps to heapsort.

I would say that if the complexity O(n*log2n) 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(n*log2n) is to be guaranteed, than the implementations use plain heapsort.

share|improve this answer

Heapsort is always O(nlogn) without the Quicksort worst case of O(n^n). 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.