CPSC 220 Fall 2007
HW 10: Heaps

1. 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
   

2. Build a max heap by placing the elements above directly into an array and then using the O(N) heap-building algorithm. Show the heap after each subtree is heapified.

3. 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.

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 big-O.

   	Build (N elements)	Enqueue	Dequeue
   Heap
   Unordered Linked List
   Ordered Array
   BST (balanced)

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