# Heaps

• March 10th, 2010, 12:10 PM
hendaz
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.

http://www.apl.jhu.edu/Classes/60520...8/Image341.gif

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.
• March 10th, 2010, 12:31 PM
helloworld922
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:

Code :

``` 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.
Code :

``` 4 1 2 5 4 6```
look at 4. 1 is smaller than 4 and 2, swap the 4 and the 1.
Code :

``` 1 4 2 1 4 6```
done building the heap.
• March 10th, 2010, 01:41 PM
hendaz
Re: Heaps
Quote:

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:

Code :

``` 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.
Code :

``` 4 1 2 5 4 6```
look at 4. 1 is smaller than 4 and 2, swap the 4 and the 1.
Code :

``` 1 4 2 1 4 6```
done building the heap.

```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.```