CSC152 2004F, Class 34: Priority Queues

Admin
* Questions on the exam?
* My office tried to destroy itself again
* Didn't get homework 33 from Kyle, Eryn, Brett, Eric.  Please don't let that happen again
* Problems with Sun's API
  Documentation is at
     http://java.sun.com/j2se/1.4.2/docs/api/
  For particular classes add
     package/package/Class.html
  For example
     http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html
     http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Object.html

Overview
* Priority queue basics
* Java Detour: Abstract classes
* Implementing priority queues
* Efficiency of those implementations
* A list ADT (if there's time)

/Exam Questions/

* What might a comparator that you'd plug in to binary search look like?

public class PointComparator
	implements Comparator
{
	/**
	 * Order two points in terms of their distance from
	 * the origin.
	 */
	public int compare(Object p, Object q)
	{
		Point pp = (Point) p;
		Point pq = (Point) q;
		double diff = pp.distanceFromOrigin() - pq.distanceFromOrigin();
		if (Math.abs(diff) < 0.00001)
			return 0;
		else if (diff < 0)
			return -1;
		else
			return 1;
	} // compare(Object, Object)
} // class PointComparator

* Do we also have to write the equals method, given that Comparator is an interface, and it specifies an equals(Object other) method?
  * NO!  Because you get one automatically.

Another example

public class Person
{
	String lname;
	String fname;
	...
}

public class ComparePersonByName
	implements Comparator
{
	public int compare(Object p, Object q)
	{
		Person pp = (Person) p;
		Person pq = (Person) q;

		int tmp = pp.lname.compareTo(pq.lname);
		if (tmp < 0)
			return tmp;
		else if (tmp > 0)
			return tmp;
		else
			return pp.fname.compareTo(pq.fname);
	} // compare(Object, Object)

}

public class CompareBigInteger
	implements Comparator
{
	public int compare(Object p, Object q)
	{
		bp = (BigInteger) p;
		bq = (BigInteger) q;
		return p.compareTo(q);
/*
		// The following won't work because we can't
		// use < and > to compare objects.
		if (bp < bq)
			return -1;
		else if (bp == bq)
			return 0;
		else if (bp > bq)
			return 1;
 */
	} // compre(Object, Object)
}

* How should we test our binary search?
  * Create an array of BigIntegers in sorted order
  * Search for various elements using the CompareBigInteger above

  BinarySearch bs = new BinarySearcher(new CompareBigInteger());

  In isInIncreasingOrder, you can then refer to this.metric

/Priority Queues/

* The third of the important linear structures
* Policy: get() returns the "highest priority" element.
* Standard Java ways of prioritizing:
  * Include a java.util.Comparator and use the one the comparator calls smallest  SAM CHOOSES THIS ONE!
  * Only put Comparables in the linear structure (and use the smallest)
  * Either of the preceding two, using the largest

/It's Time to Write an Interface/

* put, get, peek, isEmpty() come from extending Linear
* How do we state that "when you create a PriorityQueue, you specify an order on the elements"?
* Normal, class-based answer: Put it in the constructor.
* Problem: Interfaces don't have constructors!
* Bad solution: Make PriorityQueue a class.
public class PriorityQueue
	implements Linear
{
	Comparator compare;
	public PriorityQueue(Comparator _compare)
	{
		this.compare = _compare;
	} // PriorityQueue(Comparator)
} // PriorityQueue
* How do we write put(Object), get(), peek(), and isEmpty(), given that we have not yet worried about the details of the implementation?
* Java's cool solution: Abstract classes
  * Like classes, abstract classes can specify fields, constructors, and definitions of methods
  * Like interfaces, abstract classes can leave some methods declared but undefined
* How to do it?
  * Use the keyword 'abstract' before the keyword 'class'
  * Use the keyword 'abstract' before the type of each method you declare
public abstract class PriorityQueue
	implements Linear
{
	protected Comparator compare;
	protected PriorityQueue(Comparator _compare)
	{
		this.compare = _compare;
	} // PriorityQueue(Comparator)
} // PriorityQueue
* Note: In many cases, it's good to make the constructor and the fields "protected", since you expect to subclass this and you expect the subclasses to use the field
  * Protected: Accessible to everything in the same package *plus* any subclasses

/How might we impement priority queues?/

* A lot like ArrayBasedQueue, except that get() searches for the smallest value (swaps last value into its place before returning)
  put() takes O(1) [with a big enough array]
  get() takes O(n) 
* A lot like ArrayBasedQueue or LinkedQueue, except that put() makes sure that things are kept in order
  * get() simply grabs the first thing ; takes O(1)
  * put() has to find the place in which to put the thing; takes O(n)
    * What if we do binary search?  
      * Our underlying data structure must use an array (otherwise it's hard to find the middle)
      * Finding the position to insert the value is O(logn)
      * Shifting the stuff left or right to make room is O(n)
* Neither is very good.  Can we do better?
* Claveria says "use a tree"
  * A tree is like a list, except highly nested
  * A list is either
    * Empty
    * Cons of value and a list
  * A binary tree is either
    * Empty
    * Make-tree of a left subtree, a value, and a right subtree
  * The height of a fairly complete tree is O(logn)
* CLaveria's idea, continued:
  * Make sure that the value in a node is smaller than the values in its subtrees
  * Needs some way to keep the tree in this form
* Claveria hopes:
  * put is O(logn)
  * get is O(logn)
* Why is that more efficient?  Suppose we do n puts followed by n gets
  * get finds smallest: O(n^2)
  * put keeps in order: O(n^2)
  * Claveria's tree solution: O(nlogn)
* Why do n puts followed by n gets?
  * Sorting!
* We will return to this on Wednesday

HAVE A GOOD DAY!  Get some energy!