CSC152 2006S, Class 31: Priority Queues

Admin:
* Reading for Friday (Heaps) ready Thursday
* Few of you did today's homework.  Boo.
* Today is group live coding

Overview:
* Philosophy
* Applications
* Methods
* Implementation(s)

Philosophy:
* Linear structures where the get returns the "highest priority"
* How do we determine priority?
  * Include it in the put method  
    * put(T val, int prio)
    * Does not match linear structure put(T val)
  * Compare things!
    * Use a Comparator for the comparison metric.
      public class ImplementationofPriorityQueue
      {
        Comparator metric;
        public ImplementationOfPriorityQueue(Comparator _metric)
        {
          this.metric = _metric;
        } 
    * Many objects provide a compareTo method
 public interface Comparator<T>
 {
   /**
    * Compare a to b.  Return
    *  * a negative number if a < b
    *  * zero, if a == b
    *  * a positive number if a > b
    */
   public int compare(T a, T b);
  * Normal view: Smallest = "highest priority"

Applications:
* We like linear structures
* To do lists are organized according to priority 
  * High priority: CS, Throw things at Danny Zamora
  * Medium priority: Eat, Sleep, Chat with Friends
  * Low priority: Homework for other classes
* Alphabetizing/Sorting
  * Easy sorting algorithm: Shove everything in, take it out in order

Methods for Linear Structures (and, therefore, Priority Queues):
* T get()
* void put(T val)
* boolean isEmpty()
* T peek() // Skipped

Implementatation:
* You can use a vector or linked nodes
* You could organize them when put or when you get
* Vector of Vectors  // Too complicated

* Vector + organize when put: 5.5
* Vector + search for smallest (highest priority): Many
* Nodes + organize when put: 4
* Nodes + search for smallest (highest priority): 4