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

1. ## 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. ## 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. ## Re: Heaps

Originally Posted by helloworld922
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.
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. ## 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.```