Data Structures and Algorithms: Priority Queues! includes Priority Queue ADT, Total Order Relations, Entry ADT, Comparator ADT, Priority Queue Sorting, Sequence-based Priority, Selection-Sort. | Data Structures and Algorithms
Priority Queues! Outline" • Priority Queues! • Heaps! • Adaptable Priority Queues! Phạm Bảo Sơn - DSA Priority Queues " Priority Queue ADT " • A priority queue stores a collection of entries! • Each entry is a pair
(key, value)! • Main methods of the Priority Queue ADT! – insert(k, x)
inserts an entry with key k and value x! – removeMin()
removes and returns the entry with smallest key! Phạm Bảo Sơn - DSA • Additional methods! – min()
returns, but does not remove, an entry with smallest key! – size(), isEmpty()! • Applications:! – Standby flyers! – Auctions! – Stock market! Total Order Relations " • Keys in a priority • Mathematical concept queue can be of total order relation ≤! arbitrary objects – Reflexive property:
x≤x on which an order is defined! – Antisymmetric property:
x ≤ y ∧ y ≤ x ⇒ x = y! • Two distinct – Transitive property:
entries in a priority x≤y∧y≤z⇒x≤z queue can have the same key Phạm Bảo Sơn - .
