CSC300: Lecture 9 (Priority Queues and Heaps (2.4, 6.1))

Contents [0/2]

Homework [1/2]
Ungraded HW [2/2]

Homework [1/2]

+ Read Algorithms through the end of 2.5 (including 2.2,2.3)
  You should pay closer attention to 2.2 than 2.3 since mergesort will
  be on the final exam, but quicksort will not.

+ Do these problems on paper, but don't hand them in:
  Be sure to do the starred ones.
    2.4.2 (Don't confuse find-the-max and remove-the-max)
    2.4.4
    2.4.5

    2.4.9* (Draw min heaps.)
    2.4.11 (Also say why.  Don't confuse find-the-max and remove-the-max)
    2.4.12 (Also say why.  Don't confuse find-the-max and remove-the-max)
    2.4.15* (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* (Argue that your solution is constant time/space.)

+ Do the MyDeckSort assignment and hand in MyDeckSort.java
  Your goal is to implement the sort(MyDeck) method of MyDeckSort.
  You can use only the public method of MyDeck.
  You should not change the functionality of MyDeck.
  Hand in only MyDeckSort.java

  This is based on problem 2.1.14 from the text.

  To get started, download the zip file from d2l.
  Unzip and put MyDeck and MyDeckSort in algs21 package.
  You need only edit MyDeckSort.

  The Deck class has the following API:
  
    MyDeck (int N)                 // create a randomized Deck of size N
    int size ()                    // return the size of N
    int ops ()                     // return the number of operations performed on this Deck
    boolean topGreaterThanNext ()  // compare top two items
    void swapTopTwo ()             // swap top two itens
    void moveTopToBottom ()        // move top item to bottom
    void isSorted ()               // check if isSorted (throws exception if not)

--------------------
MyDeckSort Hints:

Assume that the deck d has d.size() cards.
So you might say:

for (int i=0; i<d.size(); i++) {
  if (d.topGreaterThanNext()) {
     d.swapTopTwo ()
  }
  d.moveTopToBottom ()
}


Note that you can go through the whole deck using a loop:

for (int i=0; i<d.size(); i++) {
  ...
  d.moveTopToBottom ()
}

You can also go through the deck d.size() times!

for (int i=0; i<d.size(); i++) {
  for (int j=0; j<d.size(); j++) {
    ...
    d.moveTopToBottom ()
  }
}

You can do different things at different point of the process!

for (int i=0; i<d.size(); i++) {
  for (int j=0; j<i; j++) {
    ...
    d.moveTopToBottom ()
  }
  for (int j=i; j<d.size(); j++) {
    ...
    d.moveTopToBottom ()
  }
}

Ungraded HW [2/2]

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 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