| Contents [0/3] |
| Homework (Heap Problems) [1/3] |
| HW Answers [2/3] |
| Quiz Answers [3/3] |
(Click here for one slide per page)
| 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.)
| HW Answers [2/3] |
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. 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.) We skip the 0 element:
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; }
Here we are comparing each child to it's parent. Doing this the other way is trickier. Is the following correct?
private boolean isMinHeap() { for (int i = 1; i <= (a.length-1)/2; i++) { if ( a[i*2] < a[i]) return false; if (i*2+1<a.length && a[i*2+1] < a[i]) return false; } return true; } // for comparison: private boolean isSorted() { for (int i = 1; i < a.length-1; i++) if (a[i+1] < a[i]) return false; return true; }
Here are some examples: a==[0,1] a.length==2 (a.length-1)/2==0 a==[0,1,2] a.length==3 (a.length-1)/2==1 a==[0,1,2,3] a.length==4 (a.length-1)/2==1 a==[0,1,2,3,4] a.length==5 (a.length-1)/2==2 a==[0,1,2,3,4,5] a.length==6 (a.length-1)/2==2
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.) We add a field, and modify the insert method.
private K min; public void insert(K x) { if (N >= pq.length - 1) resize(2 * pq.length); if (isEmpty() || less(x, min)) min = x; //<<<===== This is new pq[++N] = x; swim(N); } public K min() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); return min; }
Annoyingly, the less method that the book provides takes array indices, rather than values. So we need to add a method for comparing values:
private boolean less(K x, K y) { if (comparator == null) { return x.compareTo(y) < 0; } else { return comparator.compare(x, y) < 0; } }
If you use the same stragegy to provide a max for FixedPQHeap, you get this:
private double max; public double max() { if (N <= 0) throw new Error("Underflow"); return max; } public void insert(double x) { if (x == 0) throw new Error ("No zeroes allowed"); if (N >= a.length-1) throw new Error("Overflow"); if (N == 0 || x > max) max = x; //<<<===== This is new N++; a[N] = x; swim(N); }
| Quiz Answers [3/3] |
All heaps are max oriented
12
11 03
08 10 00 02
04 05 07 ** ** ** ** **
Insert: 1
12
11 03
08 10 00 02
04 05 07 01 ** ** ** **
Insert: 9
12
11 03
08 10 00 02
04 05 07 01 09 ** ** **
12
11 03
08 10 09 02
04 05 07 01 00 ** ** **
12
11 09
08 10 03 02
04 05 07 01 00 ** ** **
Insert: 6
12
11 09
08 10 03 02
04 05 07 01 00 06 ** **
12
11 09
08 10 06 02
04 05 07 01 00 03 ** **
09
08 07
05 06 00 02
01 04 03 ** ** ** ** **
remove 9
03
08 07
05 06 00 02
01 04 ** ** ** ** ** **
08
03 07
05 06 00 02
01 04 ** ** ** ** ** **
08
06 07
05 03 00 02
01 04 ** ** ** ** ** **
remove 8
04
06 07
05 03 00 02
01 ** ** ** ** ** ** **
07
06 04
05 03 00 02
01 ** ** ** ** ** ** **
remove 7
01
06 04
05 03 00 02
** ** ** ** ** ** ** **
06
01 04
05 03 00 02
** ** ** ** ** ** ** **
06
05 04
01 03 00 02
** ** ** ** ** ** ** **
07
04 02
03 05 08 01
06 09 00 ** ** ** ** **
07
04 02
09 05 08 01
06 03 00 ** ** ** ** **
07
04 08
09 05 02 01
06 03 00 ** ** ** ** **
07
09 08
04 05 02 01
06 03 00 ** ** ** ** **
07
09 08
06 05 02 01
04 03 00 ** ** ** ** **
09
07 08
06 05 02 01
04 03 00 ** ** ** ** **
Revised: 2024-03-12 13:54