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?
The proposal is to keep all the values in a queue/stack and to separately
keep the max value inserted so far. So if you were to implement this,
you would have fields something like the following (without generics):
class CrappyPQ {
Stack s;
Comparable maxSoFar;
void insert (Comparable x) {
s.push (x);
if (x.compareTo(maxSoFar) > 0) maxSoFar = x;
The problem is that the CrappyPQ must support the delete operation, so
when you delete the max it will take you linear time to find the new max
in the stack or queue.
2.4.4
Is an array that is sorted in decreasing order a max-oriented heap?
Yes.
N.B. A max-oriented heap has the property that each child element of
element k, which are found at element 2k and (2k + 1), is smaller
the value of element k in the ordering used by the heap. An array
sorted in decreasing order has this property.
However, it should be noted that not all max-ordered heaps have this
property.
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.
MAX HEAPS:
------------------------------------------------------------------
| E | E | E | E | E | E |
| D C | D C | D B | D B | D A | D A |
| B A | A B | A C | C A | B C | C B |
------------------------------------------------------------------
| E | E | |
| C D | C D | |
| B A | A B | |
------------------------------------------------------------------
| B | B | |
| B A | A B | |
| A A | A A | |
------------------------------------------------------------------
MIN HEAPS:
------------------------------------------------------------------
| A | A | A | A | A | A |
| B C | B C | B D | B D | B E | B E |
| D E | E D | E C | C E | D C | C D |
------------------------------------------------------------------
| A | A | |
| C B | C B | |
| D E | E D | |
------------------------------------------------------------------
| A | A | A | |
| A A | A B | A B | |
| B B | A B | B A | |
------------------------------------------------------------------
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)
unordered array, because cost of insert is constant
or heap, because cost of insert is logarithmic
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)
heap or ordered array, because cost of find-max is constant
2.4.15*
Design a linear-time certification algorithm to check whether an array a[]
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.)
private boolean isMinHeap() {
for (int i = 2; i < a.length; i++)
if (a[i] < a[i/2]) return false;
return true;
}
// for comparison:
private boolean isSorted() {
for (int i = 2; i < a.length; i++)
if (a[i] < a[i-1]) return false;
return true;
}
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.)
Add an int field to the MaxPQ class to hold the index where the minimum
element is located. As elements are inserted, update this field if applicable.
Updating this field during insertion can be done in constant time. Reading this
field in the min() method can be done in constant time. The amount of space
needed to store the index of the min is a 4-byte int in Java, which is a
constant amount of space.
