A queue removes items in arrival order. A priority queue removes the item with highest priority according to its ordering rule. This is useful when the next item to process should be based on importance, not time of arrival.
Priority is not insertion order
If numbers are ordered from smallest to largest, the smallest number may be removed first even if it was added last. This surprises students who expect queue behavior.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(8);
pq.add(2);
pq.add(5);
System.out.println(pq.remove());This prints 2 because Java's default priority queue for integers removes the smallest value first.
Where heaps fit
A heap is the structure commonly used to implement a priority queue efficiently. Students do not need to memorize every internal detail at first, but they should know that adding and removing are much faster than repeatedly sorting the whole list.
Common uses
- Task scheduling by priority.
- Finding the next shortest tentative path.
- Keeping the top k values.
- Event simulations where the next event time matters.
Practice idea
Trace a priority queue by writing the set of values after each add and the value removed after each remove. Do not rely on the printed internal heap order; focus on removal priority.