The Algorithm Design Manual Second Edition

3.5

Priority Queues

Many algorithms process items in a specific order. For example, suppose you must

schedule jobs according to their importance relative to other jobs. Scheduling the

1. How can you sort in O(n log n) time using only insert and in-order traversal?

2. How can you sort in O(n log n) time using only minimum, successor, and

insert?

3. How can you sort in O(n log n) time using only minimum, insert, delete?

---

84

3 .

D A T A S T R U C T U R E S

jobs requires sorting them by importance, and then evaluating them in this sorted

order.

Priority queues are data structures that provide more flexibility than simple

sorting, because they allow new elements to enter a system at arbitrary intervals.

It is much more cost-effective to insert a new job into a priority queue than to

re-sort everything on each such arrival.

The basic priority queue supports three primary operations:

• Insert(Q,x)– Given an item x with key k, insert it into the priority queue Q.

• Find-Minimum(Q) or Find-Maximum(Q)– Return a pointer to the item

whose key value is smaller (larger) than any other key in the priority queue

Q.

• Delete-Minimum(Q) or Delete-Maximum(Q)– Remove the item from the pri-

ority queue Q whose key is minimum (maximum).

Many naturally occurring processes are accurately modeled by priority queues.

Single people maintain a priority queue of potential dating candidates—mentally

if not explicitly. One’s impression on meeting a new person maps directly to an

attractiveness or desirability score. Desirability serves as the key field for inserting

this new entry into the “little black book” priority queue data structure. Dating is

the process of extracting the most desirable person from the data structure (Find-

Maximum), spending an evening to evaluate them better, and then reinserting

them into the priority queue with a possibly revised score.

Take-Home Lesson: Building algorithms around data structures such as dictio-

naries and priority queues leads to both clean structure and good performance.