The Priority Queue: When First In Is the Wrong Rule

What it is not

Three things a priority queue is not, each of which students assume:

It is not a sorted list. It never produces the whole collection in order, and it does not need to. It answers one question: what is the best item right now. Keeping everything sorted would cost more than necessary, which is chapter 80's measurement.

It is not a queue with a sort. Sorting on every insertion is one possible implementation and a poor one.

It does not keep arrival order among equal priorities. Two jobs of the same urgency may come out in either order, unless the implementation is deliberately made stable by adding the arrival number as a tie-break, which is exactly what the counter does in the program above.

That last point matters in practice: without it, a job of ordinary priority can be overtaken repeatedly and wait for ever, which is called starvation.

Starvation, demonstrated

import heapq

pq, counter = [], 0


def arrive(name, urgency):
    global counter
    heapq.heappush(pq, (urgency, counter, name))
    counter += 1


arrive("ordinary job", 5)

served = []
for round_number in range(1, 7):
    arrive("urgent %d" % round_number, 1)      # an urgent job arrives each round
    urgency, _, name = heapq.heappop(pq)
    served.append(name)

print("an ordinary job arrived FIRST, then an urgent job arrived every round.")
print()
print("served in this order:")
for name in served:
    print("   ", name)
print()
print("the ordinary job has still not been served:",
      any(name == "ordinary job" for _, _, name in pq))
print("it has been waiting for", len(served), "rounds, and will wait for ever")
print("as long as urgent work keeps arriving. this is STARVATION.")

an ordinary job arrived FIRST, then an urgent job arrived every round.

served in this order:
    urgent 1
    urgent 2
    urgent 3
    urgent 4
    urgent 5
    urgent 6

the ordinary job has still not been served: True
it has been waiting for 6 rounds, and will wait for ever
as long as urgent work keeps arriving. this is STARVATION.

The ordinary job arrived first and has still not run. A plain queue cannot starve anything, because nothing can overtake. A priority queue can, and that is the price of the rule.

The standard fix is ageing: raise an item's priority the longer it waits, so that anything waiting long enough eventually becomes urgent. Operating systems do this, and it is worth a line in an answer.

Quick revision

• A priority queue removes the item of best priority rather than the oldest.
• Min priority queue removes the smallest key (costs, distances, deadlines); max removes the largest

(scores, importance). Say which.

• Measured: an alarm waited 18 units in a queue and 0 in a priority queue, on identical input.
• It is not a sorted list, not a queue with a sort, and it does not preserve arrival order among equal

priorities unless a tie-break is added.

• Adding the arrival number as a tie-break makes it stable.
• A priority queue can starve a low priority item, which a plain queue cannot; the fix is ageing, raising

an item's priority as it waits.

Test yourself

1. Define a priority queue. A collection where each item carries a priority, and the removal operation always removes an item of the best priority.

2. What is the difference between a min and a max priority queue, and which is used for Dijkstra? A min priority queue removes the smallest key, a max one the largest. Dijkstra needs the smallest distance, so it uses a min priority queue.

3. Why is "highest priority" an ambiguous phrase? Because priority 1 usually means most urgent, so the most important item has the smallest number. The convention must be stated.

4. Give three things a priority queue is not. It is not a sorted list, it is not a queue with a sort on every insertion, and it does not preserve arrival order among items of equal priority.

5. What is starvation, and can a plain queue suffer it? An item never being served because higher priority items keep arriving. A plain queue cannot starve anything, since nothing can overtake.

6. How is starvation prevented? By ageing: raising an item's priority the longer it has waited, so anything waiting long enough eventually becomes urgent enough to be served.