CPSC 220 Fall 2005
HW 15: More Heaps
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.
- 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.
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.
- Find the error and explain what is wrong.
- Try to correctly justify the O(N) time (which is correct).
- 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.