10

Quicksort outperforms Heapsort in practice. Mergesort is the only stable one of the 3 (in plain vanilla implementations). So it's either quicksort or mergesort that'd get used depending on the situation at hand (in-place in memory or external sorting etc.,)

So is there ever a case where the heap data structure is indeed used for sorting? No matter how much I 'Google' or try to come up with applications, almost always one chooses merge/quick-sort over heapsort. I've never encountered a case where heap sort is actually used in my professional life either. What would actually be a good use-case for heapsort in practice (if at all), out of curiosity?

PhD
  • 11,202
  • 14
  • 64
  • 112
  • 3
    This is a very interesting question, please leave a comment as to why it should be closed. – David Titarenco Dec 30 '12 at 01:25
  • Please provide a reason for voting for 'closing' the question. This is a legitimate programming question, IMHO. – PhD Dec 30 '12 at 01:26
  • As it's not a question with a "correct" answer it should be, at best, community wiki. The close votes so far have all been for "As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or specific expertise, but this question will likely solicit debate, arguments, polling, or extended discussion." The portion after the "but" is what is important here. – Donnie Dec 30 '12 at 01:31
  • @Donnie - I think there is a correct answer to this problem. It's either a yes or a no with reasons. I don't think it'd solicit debate as to which algorithm to use; but more as objectively asking/answering where exactly would heapsort be the best fit in practice. That does have a correct (subjective) answer, IMO. – PhD Dec 30 '12 at 01:34
  • That's a discussion, not a Q&A question. As noted in the close reason. – Donnie Dec 30 '12 at 01:37
  • Also as noted in your comments to the first question. "Well, that's a good point, but etc etc" – Donnie Dec 30 '12 at 01:38
  • @Donnie - Please make this a community wiki in that case. It's valuable to know this, in my opinion. (Or move this to cs.stackexchange?) – PhD Dec 30 '12 at 01:38
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/21887/discussion-between-phd-and-donnie) – PhD Dec 30 '12 at 01:42
  • I've used it as a part of priority queue -based solution http://stackoverflow.com/questions/2486093/millions-of-3d-points-how-to-find-the-10-of-them-closest-to-a-given-point Python uses a heap for heapq.nsmallest(), heapq.nlargest() function that is used in `collections.Counter().most_common(n)` – jfs Dec 30 '12 at 03:14

1 Answers1

6

Some benefits off the top of my head (will amend this list after I do some more research:

  • Almost-sorted sets benefit from being sorted by heapsort.
  • Space-conscious environments often prefer the O(1) space complexity of heapsort. Think embedded systems.
  • Huge data sets benefit from the guaranteed running time of O(nlog n) as opposed to the probable better running time of quicksort. Think medical, space, life-support, etc.
David Titarenco
  • 32,662
  • 13
  • 66
  • 111
  • 1
    I agree on the second point of embedded systems. That seems like a promising approach. But for almost-sorted sets, insertion-sort would outperform heapsort, IMO. As for point 3, even mergesort has that guarantee, leading one to fallback on it instead of heapsort. – PhD Dec 30 '12 at 01:31
  • @PhD: http://dl.acm.org/citation.cfm?id=359026 - True. I remember reading otherwise somewhere. – David Titarenco Dec 30 '12 at 01:33