Hi,

In heapsort we first create a heap using heapify.  There are 2 ways of
creating the heap.  Bottom-up and top-down.  Can someone tell me which
one is more efficient and why should we prefer one over another.

Thanks in advance

Aarti

On Sep 3, 2:27 am, Aarti <aarti.sa...@gmail.com> wrote:
>
> In heapsort we first create a heap using heapify.  There are 2 ways of
> creating the heap.  Bottom-up and top-down.  Can someone tell me which
> one is more efficient and why should we prefer one over another.
>
Hi,

This question actually has quite an interesting answer.

The top-down heapify (originally described by Williams) generally
speaking,
has a lower instruction count than the bottom-up heapify (originally
described
by Floyd). In fact, building a heap top-down takes O(n lg n) worst
case time, whereas bottom
up takes only O(n) worst case time.

As a result, all algorithms text-books recommend Floyd's approach.
However, Williams's
algorithm is generally much faster in practice, despite the fact that
it almost always
executes more instructions. This is because it has much better spatial
locality than Floyd's
algorithm (i.e. it causes far fewer cache misses). So, on modern
processors, Williams's
top-down heapify is the algorithm of choice.

A good description of the situation can be found in Chapter 3 of
Anthony LaMarca's PhD thesis
http://www.lamarca.org/anthony/pubs/thesis.pdf

Best Regards,

Nicholas Nash
http://www.netsoc.tcd.ie/~nash

On Sep 3, 7:33 am, Nicholas Nash <na...@tcd.ie> wrote:
> On Sep 3, 2:27 am, Aarti <aarti.sa...@gmail.com> wrote:
>
> > In heapsort we first create a heap using heapify.  There are 2 ways of
> > creating the heap.  Bottom-up and top-down.  Can someone tell me which
> > one is more efficient and why should we prefer one over another.
>
> Hi,
>
> This question actually has quite an interesting answer.
>
> The top-down heapify (originally described by Williams) generally
> speaking,
> has a lower instruction count than the bottom-up heapify (originally
> described
> by Floyd). In fact, building a heap top-down takes O(n lg n) worst
> case time, whereas bottom
> up takes only O(n) worst case time.
>
> As a result, all algorithms text-books recommend Floyd's approach.
> However, Williams's
> algorithm is generally much faster in practice, despite the fact that
> it almost always
> executes more instructions. This is because it has much better spatial
> locality than Floyd's
> algorithm (i.e. it causes far fewer cache misses). So, on modern
> processors, Williams's
> top-down heapify is the algorithm of choice.
>
> A good description of the situation can be found in Chapter 3 of
> Anthony LaMarca's PhD thesishttp://www.lamarca.org/anthony/pubs/thesis.pdf
>
> Best Regards,
>
> Nicholas Nashhttp://www.netsoc.tcd.ie/~nash

Thanks Nicholas.