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

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

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.

Powered by vBulletin® Version 4.2.5 Copyright © 2019 vBulletin Solutions Inc. All rights reserved.