I'm currently doing an exercise that asks to prove that Standard-Heapsort requires at fewest $\frac{1}{8} n \log(n) - O(n)$ comparisons, in its best case.

In its average case, Heapsort only requires $2n\log(n) - O(n)$ comparisons, although I don't know how to prove the best case scenario.

Can someone possibly hint me where to start with my calculation, I have no idea how to prove fewest number of comparisons, always been either worst case or most comparisons up until now.

  • $\begingroup$ This paper might be of some interest, showing how to create a construction that results in $\sim \frac{1}{2} n \log n$ moves in the best-case. Where each move requires 2 comparisons, thus taking $\sim n \log n$ comparison. This doesn't follow your $\frac{1}{8} n \log n$, but maybe a similar construction can be found to fit this. $\endgroup$ – ryan May 8 '17 at 22:43
  • $\begingroup$ Yeah I've scoured through that, I literally reaad about 10 papers on Heapsort analysis and Algorithms, it doesn't seem like there's anywhere that has a proof for this $\endgroup$ – roughosing May 9 '17 at 6:53
  • $\begingroup$ If you prove that it takes $\ge n \log n$ comparisons, then you've proven it takes $\ge \frac{1}{8} n \log n$ comparisons. Yes, you'll have to deal with the asymptotics, but it sounds like that should be doable. Rather than searching for some other existing solution that pattern-matches the expression you already have, perhaps you could try to understand the techniques in that paper and see if they are useful. $\endgroup$ – D.W. May 9 '17 at 13:51
  • $\begingroup$ I think the exercise is asking for a proof on the fewest number of comparisons, not to prove an inequality, so for some best-case heap to prove that it can be done in as few as 1/8 n log(n) comparisons. I've read through that whole paper and the re-edit from 1992, plus watched around 20 videos on Heapsort and Heapify Optimization and I'm still stumped $\endgroup$ – roughosing May 9 '17 at 14:11
  • 1
    $\begingroup$ Even easier, how many comparisons are needed when you insert the values in asc order? and how many comparisons are required to repair then? This can only be the best case (min-heap). Heapify costs O(n), when you insert the value in order you dont need a repair (except for one comparison each without traversing parents). So you need to calculate the limit of "delete-min" for a continously shrinking tree when the currently biggest value is at the root and deleteD-min again. At least that is what comes first to mind. $\endgroup$ – Sam May 9 '17 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.