Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Heaps

  1. #1
    Junior Member
    Join Date
    Mar 2010
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question Heaps

    Hi,

    I am trying to implement a bottom up heap construction. I seem to have the recursion working but im not sure how i am supposed to combine the trees at each stage. My heap is based on the arraylist complete binary tree. For example, the image below shows what I am trying to achieve initially.



    From my recursion the first number is get is 16 then 15 then 25. Which I am assuming is correct. However 16 is a new binary tree 15 is a new binary tree and then 25 will be a new binary tree. In this case 16 will be the left subtree and 15 will be the right subtree but am I right in thinking rather than the new binary just created pointing to the other binary trees it should create a new binary tree with 25 as the root and 16 and 15 as the children? Basically the question is how do I at each stage in the recursion create a new binary tree storing the elements from the subtrees?



    Thanks.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Heaps

    There should already be elements in the first three spots. To build the heap bottom-up all you need to do is move elements around.

    This is done by comparing the parent with both children (if there are two) and moving the smallest of the 3 into the parent position. You can run iterate this breadth-depth wise to build the whole heap in O(n) time (no recursion required) by running this algorithm backwards from the end of the array.

    example:

    4 5 2 1 4 6

    this looks like:

                4
         5            2
    1       4     6

    The whole bottom row don't need to be moved because there are no children.
    Look next at 2. It's bigger than both it's children (6 and no child), so it stays.
    look at 5. 1 is smaller than 5 and 4, so swap the 5 and the 1.
                4
         1            2
    5       4     6
    look at 4. 1 is smaller than 4 and 2, swap the 4 and the 1.
                1
         4            2
    1       4     6
    done building the heap.

  3. #3
    Junior Member
    Join Date
    Mar 2010
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Heaps

    Quote Originally Posted by helloworld922 View Post
    There should already be elements in the first three spots. To build the heap bottom-up all you need to do is move elements around.

    This is done by comparing the parent with both children (if there are two) and moving the smallest of the 3 into the parent position. You can run iterate this breadth-depth wise to build the whole heap in O(n) time (no recursion required) by running this algorithm backwards from the end of the array.

    example:

    4 5 2 1 4 6

    this looks like:

                4
         5            2
    1       4     6

    The whole bottom row don't need to be moved because there are no children.
    Look next at 2. It's bigger than both it's children (6 and no child), so it stays.
    look at 5. 1 is smaller than 5 and 4, so swap the 5 and the 1.
                4
         1            2
    5       4     6
    look at 4. 1 is smaller than 4 and 2, swap the 4 and the 1.
                1
         4            2
    1       4     6
    done building the heap.
    Not sure I follow your working
    what would you get for the following list:
    14,9,25,16,15,5,4,12,8,11,6,7,27,23,20?

    I'm told the correct answer would be:

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Heaps

    here's the algorithm's pseudo-code:

    1. put everything as-is into your heap array.
    2. Starting from the back, compare that element with it's two children's. Take the smallest of the three (a 'missing child' is not considered smaller).
    3. swap the smallest with the element you're currently looking at.
    4. move backwards through your array and repeat 2-4 until you've reached the front of the array.
    5. done.