# CSC300: Homework (Heap Problems)

 Contents [0/1]

 Homework (Heap Problems) [1/1]

 Homework (Heap Problems) [1/1]

No video for this week.

```+ Read Algorithms through the end of 2.5 (you can skip 2.2,2.3).

+ Do the following eight problems on paper.  Be sure to do the starred ones.

+ 2.4.2 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)

+ 2.4.4 Is an array that is sorted in decreasing order a max-oriented heap?

+ 2.4.5 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.

+ 2.4.9* 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.)

+ 2.4.11 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)

+ 2.4.12 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)

+ 2.4.15* 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.)

+ 2.4.27* 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.)
```

Revised: 2008/03/17 13:01