CPSC 220 Fall 2005
HW 15: More Heaps

1. Use the bottom-up strategy that we discussed in class to construct a min-heap from the values below. Place them in the initial tree in the order given.

   34  87  1  45  65  32  3  12  17
   

   Explain what you are doing by indicating what node you are looking at at each step and where you make exchanges.

2. The complexity to build a heap bottom-up as in #1 is O(N). This is explained in the first full paragraph on page 477 of the text. Unfortunately, there is an error in the argument.
   1. Find the error and explain what is wrong.
   2. Try to correctly justify the O(N) time (which is correct).
   Hint: The error does not have to do with the references to the heap as an array, e.g. on the third line of the paragraph, ".. start with the first non-leaf node in the array..." This is just a reference to the fact that since a heap is a complete tree, it can be stored efficiently in level order in an array -- we discussed this advantage of complete trees some time ago.

3. Given that an N-element heap can be constructed in time O(N), as opposed to O(NlogN) using the top-down method, what is the complexity of heapsort? EXPLAIN YOUR ANSWER.