CSC152 2005S, Class 28: Priority Queues

Notes:
* FOR MONDAY: THINK ABOUT HOW TO FINISH THIS IMPLEMENTATION!
* When/if Brad arrives, throw something at him
  * Brad was doing something questionable with middle-school students
  * Mr. Khannabha appears to think that CDO appointments can be made for class time
* Exams to be returned Monday
* Comments on the labs?
  * Reminder: You should try to finish the labs on your own
* Today: Some lecture/recitation to see how you think about 
  implementing data structures (since you've seen lots of 
  implementation yourself).
* No presents
* Even though I throw things at you, please do not throw bricks
  or cinderblocks through my windows

Overview:
* Description (Sam)
* Applications (Students and Sam)
* Implementations (Students)

Priority Queues: Linear Structures with ...
* Linear Structure: You put stuff in and take it out in some order
* Methods
  * get - take something out of the structure
  * put - add something to the structure
  * isEmpty - determines if there are any elements
    * Needed because it plays well with others
    * Useful for implementers who have to do something special with put in the case in which the structure is already empty
    * Don't use get or peek if the structure is empty; Hint: Programmers should often write methods to allow clients to check preconditions
  * peek - tells you about the 'next' thing in the structure, but doesn't take it out
 * A "policy" determines which object get returns
* The policy in priority queues is "smallest first" or "highest priority first"
  * How do we determine order?
  * Java's answer(s):
    * Use Comparable objects and their compareTo method
      a.compareTo(b) returns
        - negative number for "a is less than b"
	- zero for "a is equal to b"
	- positive number for "a is greater than b"
    * Use a separate Comparator object and its compare method
      c.compare(a,b) returns
        - negative number for "a is less than b"
	- zero for "a is equal to b"
	- positive number for "a is greater than b"
      * Comparators are cool because they allow us to order the same set of values in different ways
  * Rolf's "interesting" answer:
    * Compare by hash codes

Problem: Why would we want priority queues?
* Gives a useful order for some applications
  * Ordering different than the order in which they get added to the queue
  * To-do lists provide a good example
  * When you need to write a sorting algorithm, it's really helpful to have a priority queue
    * Put everything into the queue
    * Remove everything
    * Observe that it was removed in order
    * The name of the most famous variant of this sort is heap sort

Problem: How do we implement priority queues?

J method
* Shove 'em in a sequence of nodes, as in queues
* Whenever we want something, we search through the entire group until we find the lowest priority thing

E method
* Store the things in order
* The highest-priority thing is therefore the first
* Array or linked nodes?  Either way?
  * Arrays:
    * Rolf likes them
    * Nicer fooooooooor looooooooooops (four lupes)
  * Linked nodes:
    * Each node points to the node of next lower priority
    * Harder to "remove" individual values from arrays
      * Rolf, when using arrays, would put the smallest thing at the "right end" (as in stacks).  So there!
    * Not constrained by the size of your initial array
      * Rolf says we know how to make arrays larger.  So there!
 * Elijah says "I don't really want my program to slow to a stop every time it has to grow the size of the array"
* Our choice: Ignore what Rolf has to say and use linked nodes.

Are there other strategies for implementing priority queues?
* Use trees.  Sounds complicated.

Vote for our example:
* Store in order: DA WINNAH
* Search each time: DA LOSAH

In practice, we would do weeks of careful analysis to determine
which of the two was better.  In the mean time, someone would
hack together a really rolfish implementation which we would end
up using.

More seriously:
* If you mostly add, and rarely remove (e.g., Sam's grading),
  we might want something in which adding is quick.
* If you may choose different prioritizations for each "get"
  (ouch), then you should use the "search each time" strategy.