Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.franciliens.net!news.muarf.org!nntpfeed.proxad.net!proxad.net!feeder2-2.proxad.net!nx02.iad01.newshosting.com!newshosting.com!216.196.98.146.MISMATCH!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 25 Jan 2012 09:13:20 -0600
Message-ID: <4F201C13.5488@mindspring.com>
Date: Wed, 25 Jan 2012 10:13:23 -0500
From: pete <pfiland@mindspring.com>
Reply-To: pfiland@mindspring.com
Organization: PF
X-Mailer: Mozilla 3.04Gold (WinNT; I)
MIME-Version: 1.0
Newsgroups: comp.lang.c
Subject: Re: Heapsort Complexity Analysis
References: <j5rmja$6nj$1@dont-email.me> <4e8177d9$0$2823$7b1e8fa0@news.nbl.fi> <kfnliowejc7.fsf@x-alumni2.alumni.caltech.edu>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 30
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.154.216.133
X-Trace: sv3-9zEYW4KuwOVz4MBknOCvmF5eZ0HnaXO9WE6RmVnFR4T+ezGs+VaFLW5bQgaYp++ZnlpMPcxNFRnYo9e!LgtuwpISGOhvF+CU+LCqRGIO/KT6/TavJ6jTpPj+6VsUYH8vbbXlacegjYEvsvFJ+Iw0fDqxMSbk!/V2x/NF2aSg=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 1981
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:16196

Tim Rentsch wrote:
> 
> Juha Nieminen <nospam@thanks.invalid> writes:
> 
> > In comp.lang.c++ Gr <g@g.com> wrote:
> >> 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.
> > [snip]
> 
> Usually, but not necessarily always.

The best case complexity for heapsort is O(n).

The best case comparisons is (3 * (n - 1)), when (n > 2).

There are several variations on heapsort.
The one that I'm refering to here
is the heapsort described by Knuth 
in The Art Of Computer Programming,
which is the double siftdown variety.
The best case data set for that kind of heapsort
is where all of the elements of the array have the same value.

-- 
pete