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.