Heap Sort - O(logn)

This is a discussion on Heap Sort - O(logn) within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Hi Im doing a presentation on Heap Sort, and it says that the it takes O(logn) to run, and since ...

  1. #1
    Microsoft. Who? MethodMan's Avatar
    Join Date
    Mar 2002
    Posts
    1,198

    Heap Sort - O(logn)

    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

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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).

  3. #3
    Microsoft. Who? MethodMan's Avatar
    Join Date
    Mar 2002
    Posts
    1,198
    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

  4. #4
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. heap sort problem
    By Cpro in forum C++ Programming
    Replies: 2
    Last Post: 02-04-2008, 04:54 AM
  2. How do I heap sort alphabetically?
    By arih56 in forum C++ Programming
    Replies: 7
    Last Post: 12-12-2007, 01:00 AM
  3. Heap Sort
    By silicon in forum C++ Programming
    Replies: 1
    Last Post: 05-18-2005, 01:53 PM
  4. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 05:03 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21