9.2: Priority Queues

It often happens that there are a number of tasks, n, each with an associated priority. The n tasks are to be carried out in order of priority. When studying for examinations, most students review and prepare in an order of priority determined by the date of the exam. Most people read the chapters of a book in order, with priority determined by chapter numbering. In this case the situation is static, since the number of chapters does not change. Computer centers process submitted programs by attaching a priority to each and processing them in order of priority. Here the number of programs does change. This represents the usual case, where it is necessary to add new tasks with their priorities to the current collection. The general situation is covered by a priority queue.

A priority queue is a data structure with objects, their priorities, and two operations, insertion and deletion. Insertion in a priority queue means that an object with its priority is added to the collection of objects. Deletion from a priority queue means that an object with highest priority is deleted from the collection. A stack may be thought of as a priority queue with the highest priority object the one most recently added. A queue may be thought of as a priority queue with the highest priority object the earliest added.

High-level programming languages do not have priority queues directly available in their memories. It is important to be able to implement such queues, because they are of use in their own right and (as will be shown later) often appear as components of algorithms.

9.2.1 Simple Implementations

9.2.2 Using a Heap

9.2.3 Using Leftist Trees