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 { /** * 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