CPSC 220 Fall 2005
HW 15: More Heaps

Use the bottomup strategy that we discussed in class
to construct a minheap 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 bottomup 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.
 Find the error and explain what is wrong.
 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 nonleaf 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.
 Given that an Nelement heap can be constructed in time O(N), as
opposed to O(NlogN) using the topdown method, what is the complexity
of heapsort? EXPLAIN YOUR ANSWER.