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
-MethodMan-
Your Move:Life is a game, Play it; Life is a challenge, Meet it; Life is an opportunity, capture it.
Homepage: http://www.freewebs.com/andy_moog/home.html
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).
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
-MethodMan-
Your Move:Life is a game, Play it; Life is a challenge, Meet it; Life is an opportunity, capture it.
Homepage: http://www.freewebs.com/andy_moog/home.html
You don't have to use two arrays. To create a heapFor space in terms of using two arrays it will be O(n) for the new allocated array, correct?
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.
A binary heap of n elements is an array of size n right?How do I know the height of the tree is O(logn)?
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.
