Thread: 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.

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.

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: