Prev: Software for "Regular Expression" <=> NFA <=> DFA
Next: Complexity Theory for Simpletons
From: Radha on 23 Feb 2006 21:38
Hi,

Can somebody please help me understand Heap Sort. How to build a heap
and how can I prove that the worst case is nlogn?

Thank you for your help.

From: iBBiS on 24 Feb 2006 04:23
Once you understand the data structure "binary heap" and its main
operations insert() and extract_{min|max}(), it is pretty
straightforward to construct "heap sort" out of it: To sort 'n'
elements, insert them into the heap (n*insert) and then extract the
root (min or max) 'n' times to get the elements in sorted order. The
running time can be derived directly from the running time of those two
heap operations. [Btw. it is also possible to build a heap in linear
time]

Chris

From: Ben Bacarisse on 24 Feb 2006 12:42
On Thu, 23 Feb 2006 18:38:56 -0800, Radha wrote:

> Hi,
>
> Can somebody please help me understand Heap Sort.

You might take a look at:

http://www2.hawaii.edu/~copley/665/HSApplet.html

--
Ben.

From: Radha on 24 Feb 2006 16:35
Thank you Chris and Ben. I need to write a proof that the worst case is
O(nlogn). I was hoping somebody could help me with that.

Thanks!!!

From: Ben Bacarisse on 25 Feb 2006 18:37
On Fri, 24 Feb 2006 13:35:50 -0800, Radha wrote:

> Thank you Chris and Ben. I need to write a proof that the worst case is
> O(nlogn). I was hoping somebody could help me with that.

Sounds like a teaching exercise. Your library should have at least one
book with such a proof. I used to use Aho, Hopcroft and Ullman: "The
Design and Analysis of Computer Algorithms" but there must be 100s of
texts with such a proof in them.

--
Ben.

 |  Next  |  Last
Pages: 1 2
Prev: Software for "Regular Expression" <=> NFA <=> DFA
Next: Complexity Theory for Simpletons