Lists, Sets, and Priority Queues

A priority queue removes elements by priority, not by the order in which they were added.

Programming

A Line That Does Not Work Like a Line

Most people already understand a queue from everyday life. Think of a checkout line: the person who arrived first is served first. A priority queue is a collection that breaks this habit. Its elements leave in order of priority rather than in the order they arrived, so the order you add things no longer decides which one comes out next.

This article follows a trace-first approach. You will watch a small priority queue change after each add and remove call, then you will predict a result before it is revealed, and finally you will learn how to drain a queue safely without triggering an error.

Tracing a Priority Queue Step by Step

A priority queue holds a set of waiting elements. Each add call places one more element into that set. Each remove call takes out the element of minimal priority among the elements still waiting, returns it, and leaves the rest in the queue. The best way to see this is to follow the contents of the queue through a sequence of calls.

What does the priority queue hold after each add() and remove() call, and which element moves out next?

Worked example

Following one priority queue through five calls

Starting from an empty priority queue, the program calls add(5), add(2), add(8), remove(), and remove(), in that order. For integers, the smallest value has minimal priority. What does each remove() return, and what is left in the queue at the end?

1
Call add(5)
The queue now holds 5. It is the only element, so it is the element of minimal priority.
2
Call add(2)
The queue now holds 5 and 2. Adding 2 did not remove anything, so the order of arrival is still visible in the contents, but it no longer decides removal.
3
Call add(8)
The queue now holds 5, 2, and 8. Three elements are waiting.
4
First remove()
Among 5, 2, and 8, the element of minimal priority is 2. The queue returns 2 and holds 5 and 8.
5
Second remove()
Among 5 and 8, the minimal element is 5. The queue returns 5 and holds only 8.

Result

The removals return 2 then 5, and the queue still holds 8. The arrival order 5, 2, 8 did not determine the removal order.

The add and remove Methods

Definition

A priority queue removes elements by priority, not by the order in which they were added.

A priority queue offers two methods that the course material focuses on. The add method places an object into the queue. That object must be of the element type T that the queue was declared with. The remove method takes no arguments, removes the element of minimal priority, and returns it. The value returned by remove is also of type T.

The wording minimal priority is the source's own phrasing. For integers, the smallest value is the one with minimal priority in this example. The rule stays the same for any element type: remove returns the element of minimal priority. Only the meaning of minimal changes with how the elements are compared.

Feature	Plain queue	Priority queue
Real-world picture	A checkout line	A line where the most urgent waiting element is handed out first
Rule for removal	First element added is the first removed	Element of minimal priority among those waiting is removed
Given adds 5, 2, 8	The first removal returns 5	The first removal returns 2
What decides the next element	Arrival order	Priority among the elements still waiting

The same elements added in the same order can leave in different orders depending on the queue type.

After several elements are added in a particular order, in what order does remove() return them, and how does that differ from the order they were added?

Read the message sequence from top to bottom. The three add messages arrive as 5, 2, 8. The three remove messages come back as 2, 5, 8. Insertion order and removal order do not match, because each removal picks the minimal element still waiting rather than the earliest one added.

Predicting the First Removal

Before reading the answer, try to commit to a prediction. Making a prediction first is the fastest way to find out whether the priority rule is clear to you. At each step, ask two questions: what was just added, and which element now has minimal priority?

What do you think happens?

Elements 5, 2, and 8 are added to an empty priority queue, in that order. What does the first remove() call return?

Reveal answer

Answer:

Removal follows priority, not arrival order. Among the waiting elements 5, 2, and 8, the element of minimal priority is 2, so remove() returns 2 even though 5 was added first.

Draining Safely with isEmpty

The source states that remove throws an exception if the queue is empty. This means you cannot call remove as many times as you like. A program that removes elements in a fixed count can crash when the count is larger than the number of elements waiting. The safe pattern is to guard every remove call with an isEmpty check, so that remove happens only while at least one element is left.

pq.addAll(coll)
while not pq.isEmpty():
    x = pq.remove()
    process(x)

pq.addAll(coll)
while not pq.isEmpty():
    x = pq.remove()
    process(x)

Notes on the code

addAll adds every element of coll to the queue in one call
isEmpty reports whether any element is still waiting
remove is called only inside the loop body, after the check has passed
process stands for whatever work the program does with each removed element

What is the sequence of checks and actions in a loop that calls remove() only when the queue is not empty, and where does the loop exit?

Read the flowchart as a cycle. The check happens first on every pass. When the queue still holds elements, the loop calls remove, handles the returned element, and returns to the check. When the queue is empty, the loop exits without calling remove again. Because remove sits behind the check, the exception the source describes is never triggered by this loop.

Mistakes When Reading Priority Queue Code

Common mistake
Assuming the first element added is the first element removed
What it looks like
Adding 5, 2, 8 and expecting the first remove() to return 5
Why it fails
A priority queue removes the element of minimal priority among those still waiting, not the earliest arrival.
Do this instead
Find the smallest waiting element first, then predict the removal.
Common mistake
Calling remove() without checking whether the queue is empty
What it looks like
Calling remove() four times after adding only three elements
Why it fails
The source states that remove throws an exception on an empty queue.
Do this instead
Guard each remove call with an isEmpty check inside a loop.
Common mistake
Checking isEmpty after the remove call instead of before it
Why it fails
The remove call still runs on the empty queue before the check can protect it.
Do this instead
Place the isEmpty check first in the loop so remove runs only while elements remain.
Common mistake
Forgetting that the object added must be of the queue's element type T

Practice Tracing a Queue

MEDIUM

A program starts with an empty priority queue of integers. It performs add(7), add(3), add(9), add(1), remove(), add(4), remove(). Trace the contents after every call, then state what the two remove() calls return. Use the rule that the element of minimal priority is removed.

Hints

After add(7), add(3), add(9), add(1), the queue holds four elements. Which one is smallest?
Remove that element, then add 4 and find the smallest of what remains.
Your two returned values should be the two smallest elements at the moment each remove is called.

Your attempt (not saved)

Key Takeaways Review

1
A priority queue removes the element of minimal priority, not the earliest element added.
2
add places an object of the queue's element type into the queue; remove takes no arguments, removes the minimal element, and returns it.
3
For integers, the smallest value has minimal priority, so you can predict removals by finding the smallest waiting element.
4
remove throws an exception on an empty queue, so drain with addAll and a loop that checks isEmpty before each remove.

At a glance

A priority queue removes elements by priority, not by the order in which they were added.
add places an object of type T into the queue, and remove takes no arguments, removes the element of minimal priority, and returns it.
Predicting removal order means finding the minimal priority element among the elements currently waiting, at each step.
remove throws an exception on an empty queue, so guard every call with an isEmpty check inside a loop.