Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #16196

Re: Heapsort Complexity Analysis

Message-ID <4F201C13.5488@mindspring.com> (permalink)
Date 2012-01-25 10:13 -0500
From pete <pfiland@mindspring.com>
Organization PF
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>

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Heapsort Complexity Analysis Gr <g@g.com> - 2011-09-27 10:52 +0530
  Re: Heapsort Complexity Analysis Juha Nieminen <nospam@thanks.invalid> - 2011-09-27 07:14 +0000
    Re: Heapsort Complexity Analysis Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-24 16:06 -0800
      Re: Heapsort Complexity Analysis pete <pfiland@mindspring.com> - 2012-01-25 10:13 -0500
        Re: Heapsort Complexity Analysis Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-31 16:14 -0800
  Re: Heapsort Complexity Analysis Gene <gene.ressler@gmail.com> - 2011-09-27 02:45 -0700
    Re: Heapsort Complexity Analysis Patricia Shanahan <pats@acm.org> - 2011-09-27 04:11 -0700
      Re: Heapsort Complexity Analysis Gene <gene.ressler@gmail.com> - 2011-09-27 05:53 -0700
      Re: Heapsort Complexity Analysis Gr <g@g.com> - 2011-09-28 01:33 +0530
  Re: Heapsort Complexity Analysis "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-09-27 16:35 -0700
  Re: Heapsort Complexity Analysis pete <pfiland@mindspring.com> - 2011-09-27 21:08 -0400
  Re: Heapsort Complexity Analysis Kaz Kylheku <kaz@kylheku.com> - 2012-01-25 00:59 +0000
    Re: Heapsort Complexity Analysis "Ant" <not@home.today> - 2012-01-25 01:23 +0000

csiph-web