Data Structures and the Java Collections Framework, Third Edition

CHAPTER 13

Priority Queues

In this chapter, we examine the priority queue data type. A priority queue is a collection in which only the element with highest priority can be removed, according to some method for comparing elements. This restriction allows an implementation—the Java Collections Framework's PriorityQueue class—with an add method whose average time is constant. The PriorityQueue class can be enhanced by including heapSort, a fast sort method for which worstSpace(n) is constant. The chapter concludes by using a priority queue to generate a Huffman Tree—a necessary component of a popular data-compression technique called Huffman compression.

CHAPTER OBJECTIVES

1. Understand the defining property of a priority queue, and how the Java Collections Framework's PriorityQueue class violates that property.
2. Be able to perform the heap operations of siftUp and siftDown.
3. Compare Heap Sort to Merge Sort with respect to time and space requirements.
4. Examine the Huffman data-compression algorithm.
5. Determine the characteristic of a greedy algorithm.

13.1 Introduction

A variation of the queue, the priority queue is a commonplace structure. The basic idea is that we have elements waiting in line for service, as with a queue. But removals are not strictly on a first-in-first-out basis. For example, patients in an emergency room are treated according to the severity of their injuries, not according to when they arrived. Similarly, in air-traffic control, when there is a queue of planes ...