tailieunhanh - Lecture Data structures and algorithms in Java (6th edition): Chapter 9.3 - Goodrich, Tamassia, Goldwasser

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 .