PDA

View Full Version : Heap Sort - O(logn)



MethodMan
11-14-2002, 07:14 PM
Hi
Im doing a presentation on Heap Sort, and it says that the it takes O(logn) to run, and since there are n items it is O(n*logn). But I have no idea how they get that it takes O(logn) to run in the first place.

Can anyone explain this to me?
- Ive searched a lot of websites, they all have O(logn) as run time, but never explain how they achieve it.

Thanks

Nick
11-14-2002, 07:38 PM
First you actually
create the heap from the array. This takes O(n) the math
to this is kind of messy. When you have the heap what you
do is you get the maximum element in O(1). Then
you swap the maximum element with A[heap-size] decrement
heap size all this is done in O(1). You are left with heap
who's root is not necessary the maximum so you must bubble this down. Since a heap is almost a full tree with height O(lg n) this bubble down takes time O(lg n).

MethodMan
11-14-2002, 07:53 PM
Just a few clarificiations

How do I know the height of the tree is O(logn)?

Also in terms of space if this is all done in one array, in the actual sorting ill just need a few pointers.

For space in terms of using two arrays it will be O(n) for the new allocated array, correct?

Thanks

Nick
11-14-2002, 08:19 PM
For space in terms of using two arrays it will be O(n) for the new allocated array, correct?

You don't have to use two arrays. To create a heap
from an array you go from the first interior node PARENT(heap-size) and work left and up bubbling down each node.
Upperbounds on time using two arrays are the same but
that uses more space.



How do I know the height of the tree is O(logn)?

A binary heap of n elements is an array of size n right?
To find the left child index of index i you calculate i * 2.
From this you can kind of make a path following left childs. The
parent node is at index 1. Following h left childs and you
arrive at the 2^h index. But you must have
2^h <= n and this implies h <= lg(n) lg is the base 2 log a increasing function. Another way is by induction and I meant
to say full binary tree. A full tree is a tree that has
2^(h + 1) - 1 nodes.