This chapter provides knowledge of priority queues. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Priority Queues 3/19/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Priority Queues © 2014 Goodrich, Tamassia, Goldwasser Priority Queues 1 Priority Queue ADT q q q A priority queue stores a collection of entries Each entry is a pair (key, value) Main methods of the Priority Queue ADT n n insert(k, v) inserts an entry with key k and value v removeMin() removes and returns the entry with smallest key, or null if the the priority queue is empty © 2014 Goodrich, Tamassia, Goldwasser q Additional methods n n q Priority Queues min() returns, but does not remove, an entry with smallest key, or null if the the priority queue is empty size(), isEmpty() Applications: n n n Standby flyers Auctions Stock market 2 1 Priority Queues 3/19/14 Example q A sequence of priority queue methods: © 2014 Goodrich, Tamassia, Goldwasser Priority Queues 3 Total Order Relations q q Keys in a priority queue can be arbitrary objects on which an order is defined Two distinct entries in a priority queue can have the same key © 2014 Goodrich, Tamassia, Goldwasser q Mathematical concept of total order relation ≤ n n n Comparability property: either x ≤ y or y ≤ x Antisymmetric property: x ≤ y and y ≤ x ⇒ x = y Transitive property: x ≤ y and y ≤ z ⇒ x ≤ z Priority Queues 4 2 Priority Queues 3/19/14 Entry ADT q q q An entry in a priority queue is simply a keyvalue pair Priority queues store entries to allow for efficient insertion and removal based on keys Methods: n n q /** * Interface for a key-value * pair entry **/ public interface Entry { K getKey(); V getValue(); } getKey: returns the key for this entry getValue: returns the value associated with this entry © 2014 Goodrich, Tamassia, Goldwasser As a Java interface: Priority Queues 5 Comparator ADT q q q q A .
