A priority queue removes the item with the best priority, not the item that arrived first. A heap is the structure commonly used to make those priority operations efficient.
Priority queue behavior
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(8);
pq.add(2);
pq.add(5);
pq.add(1);
System.out.println(pq.remove()); // 1
System.out.println(pq.remove()); // 2Java's default priority queue for integers removes the smallest value first. The internal printed order may not look sorted, but each removal gives the next priority item.
Worked example: keep the top 3 scores
If a stream of scores arrives, sorting every time is wasteful. A small priority queue can keep only the best three scores seen so far.
public static ArrayList<Integer> topThree(int[] scores)
{
PriorityQueue<Integer> best = new PriorityQueue<>();
for (int score : scores)
{
best.add(score);
if (best.size() > 3)
{
best.remove(); // remove smallest of the kept scores
}
}
return new ArrayList<Integer>(best);
}The queue never stores more than four items before trimming back to three. For large data, this is much better than repeatedly sorting all scores.
Why heaps are efficient
A heap keeps enough order to find the next priority item quickly without fully sorting everything. Add and remove are typically O(log n). Peek is O(1). That tradeoff is ideal for scheduling, event simulations, and top-k problems.
Custom priorities
For objects, students must define what priority means. For example, a tutoring waitlist might prioritize earlier request dates, while an assignment queue might prioritize closest due date.
PriorityQueue<Task> tasks =
new PriorityQueue<>((a, b) -> a.getDueDay() - b.getDueDay());The comparator says lower due day should come first. A weak comparator can create confusing ordering, so students should test ties and equal priorities.
Practice prompt
Given event times {14, 3, 9, 3, 20}, trace the order removed from a priority queue. Then modify the top-three method to keep the three smallest values instead of the three largest.