The Priority Queue ADT

Get access to whole semester resourcesSemester Pass

Chapter Seventy-Nine

Syllabus topic Module 2, "Priority Queues & Heaps: Priority Queue ADT"

Pages 249 to 251 of 411

In one line

The priority queue ADT is insert, remove the best, and peek at the best, and the design question every implementation must answer is which of insert and remove pays the cost.

The ADT

A Priority Queue holds items, each with a priority, and gives access to an item of best priority.

Operation	Needs	Returns	Does	When it cannot
`PriorityQueue()`	nothing	an empty queue	creates it	never fails
`insert(item, priority)`	an item and a priority	nothing	adds it	overflow if bounded
`remove_best()`	nothing	an item	removes and returns one of best priority	underflow if empty
`peek_best()`	nothing	an item	returns it without removing	error if empty
`is_empty()`	nothing	true or false	is it empty	never fails
`size()`	nothing	a number	how many items	never fails

Two more appear in some books, and both are needed by Dijkstra's algorithm in chapter 98:

Operation	Does
`decrease_key(item, new)`	lowers an item's key, moving it towards the front
`merge(other)`	combines two priority queues

The naming varies: remove_best is also extract_min, extract_max, delete_min, dequeue or pop. peek_best is also find_min, top or front. An answer may use any of them consistently.

The design question

This is the part worth understanding rather than memorising.

A priority queue has two main operations, and one of them must do the work:

Pay on insert. Keep the collection sorted. Then remove_best is trivial, taking the end item, and insert must find the right position.

Pay on remove. Keep the collection unsorted. Then insert is trivial, appending, and remove_best must search for the best item.

Pay a little on both. Keep it partly ordered, enough to know where the best item is but not enough to be fully sorted. That is the heap, and it is why the heap is the answer.

Chapter 80 measures all three.

The ADT obeyed, before it is built

import heapq


class PriorityQueue:
    """The ADT, on Python's heapq, so the behaviour is visible before chapter 81
    builds the structure by hand. A min priority queue: smallest key first."""

    def __init__(self):
        self._items = []
        self._counter = 0

    def insert(self, item, priority):
        heapq.heappush(self._items, (priority, self._counter, item))
        self._counter += 1

    def remove_best(self):
        if not self._items:
            raise IndexError("remove_best from an empty priority queue: underflow")
        priority, _, item = heapq.heappop(self._items)
        return item, priority

    def peek_best(self):
        if not self._items:
            raise IndexError("peek_best at an empty priority queue: underflow")
        priority, _, item = self._items[0]
        return item, priority

    def is_empty(self):
        return not self._items

    def size(self):
        return len(self._items)


pq = PriorityQueue()
print("new: empty =", pq.is_empty(), "| size =", pq.size())

patients = [("sprained ankle", 5), ("chest pain", 1), ("flu", 4),
            ("broken arm", 2), ("headache", 5)]
for name, urgency in patients:
    pq.insert(name, urgency)
    best, priority = pq.peek_best()
    print("arrives %-16s urgency %d -> next to be seen: %s (%d)"
          % (name, urgency, best, priority))

print()
print("treating them in order:")
while not pq.is_empty():
    name, urgency = pq.remove_best()
    print("   %-16s urgency %d" % (name, urgency))

print()
try:
    pq.remove_best()
except IndexError as e:
    print("underflow:", e)

The Priority Queue ADT

new: empty = True | size = 0
arrives sprained ankle   urgency 5 -> next to be seen: sprained ankle (5)
arrives chest pain       urgency 1 -> next to be seen: chest pain (1)
arrives flu              urgency 4 -> next to be seen: chest pain (1)
arrives broken arm       urgency 2 -> next to be seen: chest pain (1)
arrives headache         urgency 5 -> next to be seen: chest pain (1)

treating them in order:
   chest pain       urgency 1
   broken arm       urgency 2
   flu              urgency 4
   sprained ankle   urgency 5
   headache         urgency 5

underflow: remove_best from an empty priority queue: underflow

The triage behaviour the practical names: the chest pain arrived second and is seen first, and it stays at the front however many patients arrive afterwards.

Note the last two: both urgency 5, and they come out in arrival order, because the counter breaks the tie. That is the stability of chapter 78, and without it the order of equal priorities would be arbitrary.

The three error conditions

Underflow: removing or peeking at an empty priority queue. Applies to every implementation.

Overflow: only where the capacity is bounded, as in an array-based heap of fixed size.

A priority that cannot be compared: a real condition in practice. Every item's priority must be comparable with every other's, or the structure cannot decide. In Python, mixing a string priority with a number raises a TypeError.

The ADT in examination form

PriorityQueue: a collection of items, each with a priority.

insert(item, priority): add the item. Overflow if bounded.

remove_best() : remove and return an item of best priority. Underflow if empty.

peek_best() : return it without removing. Error if empty.

is_empty(), size() : as usual.

Costs depend on the implementation: see chapter 80.

The last line is the one that distinguishes this ADT from the stack's and the queue's. For a stack, "every operation is O(1)" was part of the promise. For a priority queue it is not possible, and saying so is part of knowing the structure: no implementation makes both insert and remove constant.

Quick revision

The ADT: insert, remove_best, peek_best, is_empty, size; plus decrease_key and merge in some books.
Many names for the same operations: extract_min, delete_min, find_min, top.
The design question: one of insert and remove must do the work. Sorted pays on insert; unsorted pays on

remove; a heap pays a little on both.

Equal priorities come out in arbitrary order unless a counter is added as a tie-break, which makes it

The Priority Queue ADT

stable.

Underflow applies always; overflow only to a bounded implementation; and every priority must be

comparable with every other.

Unlike the stack and the queue, a priority queue cannot promise O(1) for all operations.

Test yourself

1. Write the priority queue ADT. A collection of items with priorities. insert(item, priority) adds one; remove_best() removes and returns an item of best priority, with underflow if empty; peek_best() returns it without removing; is_empty() and size() as usual.

2. Give three alternative names for remove_best. extract_min, delete_min, or pop. extract_max for a max priority queue.

3. State the design question every implementation must answer. Which of insert and remove pays the cost: a sorted collection pays on insert, an unsorted one pays on remove, and a heap pays a moderate cost on both.

4. Two items have the same priority. What determines the order they come out in? Nothing, unless the implementation adds a tie-break such as an arrival counter, which makes it stable and returns them in arrival order.

5. Why can the priority queue ADT not promise that every operation is O(1)? Because no implementation achieves it: making insertion constant forces removal to search, and making removal constant forces insertion to place the item in order.

6. Name the three error conditions. Underflow on removing or peeking at an empty queue; overflow where the capacity is bounded; and priorities that cannot be compared with one another.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue