# Class 31: Priority Queues

Back to Discussion of Exam 1. On to Heaps and Heap Sort.

Held: Wednesday, March 15, 2006

Summary: Today we investigate priority queues, linear structures in which the policy is highest-priority first, which usually translates into smallest first.

Related Pages:

Assignments

Notes:

• No homework over break.

Overview:

• Philosopy of Priority Queues.
• Aplications of Priority Queues.
• Methods for Priority Queues.
• Implementing Priority Queues.

## Philosophy of Priority Queues

• Priority queues are the third basic linear structure.
• The policy for priority queues is `get` returns the highest-priority object.
• How do we determine priority? Typically, we use the smallest or largest element.
• If the objects in our priority queue are all `Comparable` to each other, we use the `compareTo` method associated with those objects.
• We can also choose a `Comparator` to use when we create the priority queue and use its `compare` method.
• Some of you suggested having `put` take an additional parameter, the priority. I'd rather not change the signature of that method.
• The alternative strategy is to wrap the value, as in
```public class Prioritized<T>
{
T value;
int priority;
...
} // class Prioritized&tl;T>
```

## Applications of Priority Queues

• Priority queues have natural applications in task-processing systems, since they ensure that the most important tasks get accomplished first.
• Of course, they are also inherently unfair to low-priority tasks.
• Many folks use some form of priority queue for their to-do lists.
• Priority queues also provide a natural easy sorting algorithm:
• Put all the values into the priority queue.
• Remove them one-by-one.

## Priority Queue Methods

• Priority queues are simply linear structures, so they have the basic linear structure operations.
• That is,
• `void put(T val)`
• `T get()`
• `boolean isEmpty()`

## Implementing priorty queues

• Basic strategy grid:
• Use linked nodes vs. use an array
• Order values on `put` vs. order values on `get`
• Other strategies:
• A vector of vectors, with each position in the outer vector corresponding to a numeric priority (and all values of the same priority being in the vector at that space).
• Suggesters:
• Linked Nodes, Sort on `put`: Emily
• Linked Nodes, Sort on `get`: Emily
• Array: Sort on `put`: Aaron, Emily, Tony
• Array: Sort on `get`: Emily
• Vector of Vectors: Ian BR
• Non-suggesters:
• Ben, Betsy, Christine, D.L., Hak, Ian A, Kennan, Lindsay, Nii, Sam, Scott
• We're going to choose one and implement it live.

Back to Discussion of Exam 1. On to Heaps and Heap Sort.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 9 08:31:44 2006.
The source to the document was last modified on Thu Jan 12 14:58:06 2006.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2006S/Outlines/outline.31.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu