| CSC300: Homework (Heap Problems) [1/3] | |
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 correct.)