Data Structures and Algorithms in Java, 6th Edition

Chapter 9

Priority Queues

Contents

9.1 The Priority Queue Abstract Data Type

9.1.1 Priorities

9.1.2 The Priority Queue ADT

9.2 Implementing a Priority Queue

9.2.1 The Entry Composite

9.2.2 Comparing Keys with Total Orders

9.2.3 The AbstractPriorityQueue Base Class

9.2.4 Implementing a Priority Queue with an Unsorted List

9.2.5 Implementing a Priority Queue with a Sorted List

9.3 Heaps

9.3.1 The Heap Data Structure

9.3.2 Implementing a Priority Queue with a Heap

9.3.3 Analysis of a Heap-Based Priority Queue

9.3.4 Bottom-Up Heap Construction

9.3.5 Using the java.util.PriorityQueue Class

9.4 Sorting with a Priority Queue

9.4.1 Selection-Sort and Insertion-Sort

9.4.2 Heap-Sort

9.5 Adaptable Priority Queues

9.5.1 Location-Aware Entries

9.5.2 Implementing an Adaptable Priority Queue

9.6 Exercises

9.1 The Priority Queue Abstract Data Type

9.1.1 Priorities

In Chapter 6, we introduced the queue ADT as a collection of objects that are added and removed according to the first-in, first-out (FIFO) principle. A company's customer call center embodies such a model in which waiting customers are told “calls will be answered in the order that they were received.” In that setting, a new call is added to the back of the queue, and each time a customer service representative becomes available, he ...