This chapter provides knowledge of Adaptable Pq. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Locators 3/25/14 15:06 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 Adaptable Priority Queues 3 a 5 g © 2014 Goodrich, Tamassia, Goldwasser Adaptable Priority Queues 4 e 1 Entry and Priority Queue ADTs q q An entry stores a (key, value) pair Entry ADT methods: n n getKey(): returns the key associated with this entry getValue(): returns the value paired with the key associated with this entry q Priority Queue ADT: n n n n © 2014 Goodrich, Tamassia, Goldwasser insert(k, x) inserts an entry with key k and value x removeMin() removes and returns the entry with smallest key min() returns, but does not remove, an entry with smallest key size(), isEmpty() Adaptable Priority Queues 2 1 Locators 3/25/14 15:06 Example q Online trading system where orders to purchase and sell a stock are stored in two priority queues (one for sell orders and one for buy orders) as (p,s) entries: n n n n q q The key, p, of an order is the price The value, s, for an entry is the number of shares A buy order (p,s) is executed when a sell order (p’,s’) with price p’s) A sell order (p,s) is executed when a buy order (p’,s’) with price p’>p is added (the execution is complete if s’>s) What if someone wishes to cancel their order before it executes? What if someone wishes to update the price or number of shares for their order? © 2014 Goodrich, Tamassia, Goldwasser Adaptable Priority Queues 3 Methods of the Adaptable Priority Queue ADT remove(e): Remove from P and return entry e. q replaceKey(e,k): Replace with k and return the key of entry e of P; an error condition occurs if k is invalid (that is, k cannot be compared with other keys). q replaceValue(e,v): Replace with v and return the value of entry e of P. q © 2014 Goodrich, Tamassia, Goldwasser Adaptable Priority Queues 4 2 Locators 3/25/14 .
