CPSC 220 Fall 2007
HW 10: Heaps
 Build a max heap by repeated insertion of the following keys in the
order given. Show the heap after each key is inserted.
9 23 2 7 15 6 8 5 12 3
 Build a max heap by placing the elements above directly into an array
and then using the O(N) heapbuilding algorithm. Show
the heap after each subtree is heapified.
 Suppose you want the k largest elements in the heap in order; how would
you go about rearranging the array so that these are the last k element? (Note that
the entire array won't be a max heap anymore, although the first part of
it will be.) Explain your algorithm and then illustrate it by do it for
your heap in #2 and k=4.
 We talked about a heap as a way of implementing a priority queue.
Compare it to a linked list and an ordered array for the priority
queue operations by filling out the table below in bigO.
 Build (N elements)
 Enqueue
 Dequeue

Heap




Unordered Linked List




Ordered Array




BST (balanced)




 (Extra Credit) 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).