This is an old revision of the document!

We seek algorithms that improve qualitatively on brute-force search, and in general we use polynomial-time solvability. Priority queues will be useful when we are implementing the Stable Matching problem.

The Problem We discussed ho we need to maintain a dynamically changing set S. In such cases, we want to be able to add, delete, and select elements from S when the algorithm calls it. A priority queue has a priority value, or key, and each time we need to select an element from S, we want to take the one with highest priority.

A PQ is a data structure that maintains a set of elements S, in which every element has an associated value key. A motivating application of PQs is the problem of managing real-time events such as the scheduling of processes on a computer. Each process has a priority or urgency, but processes do not arrive in order