QUESTION 1:

a) Criticize the following idea: To implement find the maximum in constant time, why not use a stack or a queue, but keep track of the maximum value inserted so far, then return that value for find the maximum? (Don't confuse find-the-max and remove-the-max) b) Is an array that is sorted in decreasing order a max-oriented heap?

c) Give the heap that results when the keys E A S Y Q U E S T I O N are inserted in that order into an initially empty max-oriented heap.

d) Draw all of the different heaps that can be made from the five keys A B C D E, then draw all of the different heaps that can be made from the five keys A A A B B. (Draw min heaps.)

e) Suppose that your application will have a huge number of insert operations, but only a few remove the maximum operations. Which priority-queue implementation do you think would be most effective: heap, unordered array, or ordered array? (Also say why. Don't confuse find-the-max and remove-the-max)

f) Suppose that your application will have a huge number of find the maximum operations, but a relatively small number of insert and remove the maximum operations. Which priority-queue implementation do you think would be most effective: heap, unordered array, or ordered array? (Also say why. Don't confuse find-the-max and remove-the-max) g) Design a linear-time certification algorithm to check whether an array pq[] is a min-oriented heap. (The method MinPQ.isMinHeap does this recursively. What would an iterative solution be? You should make sure you understand this and can do it without looking at MinPQ.isMinHeap.)

h) Find the minimum. Add a min() method to MaxPQ. Your implementation should use constant time and constant extra space. (Argue that your solution is constant time/space.)