GotchaDifficulty: Advanced1 min

PriorityQueue Iteration Order: Printing Does Not Show Poll Order

A test passes for six elements and fails for seven, because a heap is not a sorted list.

A PriorityQueue only guarantees that the smallest element is at the front. Printing it, iterating it or looping over it with for shows the elements in storage order, which is not the order poll() returns them in.

A test asserts on the printed contents of a priority queue, passes for six elements and fails for seven. Printing the queue shows the elements out of order, and polling gives them back in order:

java

Queue<Integer> q = new PriorityQueue<>(List.of(5, 1, 4, 2, 8, 3, 7));

System.out.println(q);
while (!q.isEmpty()) { System.out.print(q.poll() + " "); }

text

[1, 2, 3, 5, 8, 4, 7]
1 2 3 4 5 7 8

A PriorityQueue is a heap: a structure that keeps the smallest element at the front and the rest only partly ordered, because keeping everything sorted would cost more than that one guarantee is worth.

toString, iterator (the object that walks the elements) and the enhanced for all walk the underlying array in storage order, so they show the heap's shape rather than the order things will come out.

Poll to see the order, or copy into something sorted when you need to look. Never assert on the iteration order of a priority queue.

java

List<Integer> inOrder = new ArrayList<>();
while (!q.isEmpty()) { inOrder.add(q.poll()); }

← → move through sections and cards