Data Structures and Algorithms in Python

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 Composition Design Pattern

9.2.2 Implementation with an Unsorted List

9.2.3 Implementation 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 Array-Based Representation of a Complete Binary Tree

9.3.4 Python Heap Implementation

9.3.5 Analysis of a Heap-Based Priority Queue

9.3.6 Bottom-Up Heap Construction

9.3.7 Python's heapq Module

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 Locators

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 or she is connected with the call that ...