Heapsort Complexity Analysis

[Gr]

Heapsort worst case complexity is obviously nLogN.
However, what's the best case complexity?
Can we consider that the siftup(fixup) & siftdown(fixdown) operations
will be done in constant time, so the complexity of heapsort would be n?
Is this correct - if not what's the best case scenario for heapsort?

 

[Juha Nieminen]

Heapsort worst case complexity is obviously nLogN.
However, what's the best case complexity?

Every time the smallest (iow. first) element of the heap is removed,
the heap needs to be re-heapified, which is always a log(n) operation.
You need to do this n times.

 

[Gene]

Heapsort worst case complexity is obviously nLogN.
However, what's the best case complexity?
Can we consider that the siftup(fixup) & siftdown(fixdown) operations
will be done in constant time, so the complexity of heapsort would be n?
Is this correct - if not what's the best case scenario for heapsort?

There are n! ways of ordering the input. Discovering the order of the
input is equivalent to sorting. (That is, if you know the order of
the input, it's trivial to sort. If you have a way of sorting, just
do it indirectly, and you have the original order of the input.) A
binary comparison can't eliminate more than half of the possible input
orderings at a time. So comparison sorting is Omega(log_2 n!) =
Omega(n log n). Look up "information theoretic sort time bound" for
the details. And prepare for people who will note this isn't a C
question.

 

[Gene]

I'm not sure whether that is the answer to the question being asked.

Consider bubble sort. If the input is already in sorted order, it does
only n-1 comparisons.

I think that may be what the OP meant by "best case scenario". Is there
some input pattern that makes heapsort fast, the way pre-sorted input
makes bubble sort fast?

Patricia

On second reading I guess you're right. I read "best case complexity"
as "lower asymptotic bound." Certainly the normal array
implementation has no hope of an input ordering with constant number
of comparisions per element because it intentionally brings a leaf of
the heap to the top and sifts it back down on each iteration. A
specially structured heap - with maybe some children intentionally
missing to limit sifting range - might change this.

 

[Gr]

I'm not sure whether that is the answer to the question being asked.

Consider bubble sort. If the input is already in sorted order, it does
only n-1 comparisons.

I think that may be what the OP meant by "best case scenario". Is there
some input pattern that makes heapsort fast, the way pre-sorted input
makes bubble sort fast?

Yes, that's what I was looking at.
Would the fixDown and/or fixDown become constant time for some
particular order of input which would make the heapsort O(n) as a best
case scenario.

 

[Kaz Kylheku]

Heapsort worst case complexity is obviously nLogN.
However, what's the best case complexity?

You know how to connect to an NNTP server, but not use Google?

What institution let you roam out into the streets?

Millions of people successfully Google every day who have never heard of
Usenet.

The Wikipedia page on Heapsort has the following table:

Class Sorting algorithm
Data structure Array
Worst case performance O(n log n)
Best case performance Ω(n),O(n log n)[1]
Average case performance O(n log n)
Worst case space complexity O(n) total, O(1) auxiliary

This is wrong. Or rather, the omega(n) lower bound, while technically true, is
not tight enough to be the useful answer. Yes, it's obvious that heapsort
works no *faster* than omega(n).

A citation is given: [1] pointing to "The Analysis of Heapsort", by R. Schaffer
and R. Sedgewick. This text is not available for free, but from what is stated
in the abstract, it is obvious that the paper gives a tighter analysis.

Furthermore, there is this StackOverflow posting by someone summarizing the
main arguments from the paper:

http://stackoverflow.com/questions/4589988/lower-bound-on-heapsort

It looks as though heap sort is theta(n log n). I.e. it has no better
or worse behavior for any inputs.

All courtesy of using search engines.

Before you go, let's burp you, too, and change your diaper!