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!