skip to content

Why is iterating over a PriorityQueue not the same as getting elements in sorted order?

level: middleimportance: must knowfreq 62%

answer

  1. Heap = partially ordered array, not sorted
  2. Only the head (index 0) is guaranteed min
  3. Iterator/for-each/toString walk raw array order
  4. poll() in a loop drains in order
  5. Sort a copy if you must keep the queue

basics

~20 s

Iterating (for-each, iterator, toArray, toString) walks the internal heap array, which is only partially ordered - just the head is guaranteed smallest. Repeatedly calling poll() drains them in priority order; sorting a copy leaves the queue intact.

solid answer

~50 s

A common gotcha: only the *head* of a PriorityQueue is guaranteed to be the minimum. Internally it's a binary heap stored in an array, and a heap only maintains the *heap property* (each parent is <= its children), not a full sort. So when you iterate - via the iterator, an enhanced for loop, toArray(), stream(), or toString() - you traverse the raw array in no particular sorted order; you'll often see the smallest first but the rest can appear shuffled. The documentation explicitly says the iterator does not guarantee any ordering. To read elements in priority order from the queue itself, drain it with poll() (or remove()) in a loop, which removes the head and restores the heap each time. To keep the queue, poll a copy, or sort a copy with the queue's comparator; a plain sorted stream uses natural ordering.

go deeper

for a junior

Knows iterating doesn't print sorted order and that repeated poll() gives sorted output.

for a middle

Explains the heap is a partially ordered array where only the root is guaranteed minimum, and names which operations (iterator/toString/stream) ignore order.

for a senior

Ties it to the heap property and sift-down, explains the O(log n) trade-off, and gives non-destructive sorted-read workarounds.

for a principal

Discusses contract/Javadoc guarantees, when to prefer a TreeSet for ordered iteration, and the API-design rationale for the weak ordering guarantee.

## The surprising behavior ``` PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.addAll(List.of(5, 1, 4, 2, 3)); System.out.println(pq); // e.g. [1, 2, 4, 5, 3] - NOT sorted! for (int x : pq) System.out.print(x); // also not sorted ``` Many people expect a for-each over a PriorityQueue to print `1 2 3 4 5`. It does not. Understanding *why* requires knowing how the queue is stored. ## How a binary heap is stored A `PriorityQueue` is backed by a plain array that represents a **binary heap**. A binary heap is a complete binary tree where every node satisfies the **heap property**: in a min-heap, each parent is **<= both of its children**. The tree is mapped onto an array by index: the element at index `i` has children at `2i+1` and `2i+2` and parent at `(i-1)/2`. Crucially, the heap property is a *local* guarantee about parent-vs-child only. It says **nothing** about the order of siblings or of cousins. So the array is **partially ordered**: index 0 (the root) is the global minimum, but the rest can be in many valid arrangements. For example `[1, 2, 4, 5, 3]` is a perfectly valid min-heap - 1<=2 and 1<=4, 2<=5 and 2<=3 - even though the array isn't sorted. ## What iteration actually does In OpenJDK the `iterator()`, enhanced `for`, `toArray()`, `stream()`, and `toString()` all walk that backing array **in array index order**, apart from an element an `iterator.remove()` had to defer. Because the array is only heap-ordered, you get an order that starts with the minimum but is otherwise arbitrary. The Javadoc states plainly that the Iterator and the Spliterator "are not guaranteed to traverse the elements of the priority queue in any particular order", and that `toArray()`'s elements "are in no particular order". ## Getting sorted output from the queue itself Among the queue's own operations, the ordering guarantee lives in `poll()` / `remove()`, which always take the head. Each `poll()`: 1. takes the root (current minimum), 2. takes the last array element out, leaving a hole at the root, and 3. **sift-downs** that element from the root (moves the smaller child up repeatedly, then writes the element once it fits) to restore the heap property. So successive polls yield the global minimum, then the next minimum, and so on - a true sorted sequence. This is the heapsort idea. The cost is that polling **empties** the queue. ``` while (!pq.isEmpty()) System.out.print(pq.poll() + " "); // 1 2 3 4 5 ``` ## Practical workarounds - To iterate sorted *without* destroying the queue: poll a **copy** (`new PriorityQueue<>(pq)`, which keeps the comparator), or copy to a list and call `list.sort(pq.comparator())`, where a null comparator means natural ordering. - `pq.stream().sorted()` and the Javadoc's suggestion `Arrays.sort(pq.toArray())` use natural ordering, not the queue's comparator: on a reverse-order queue holding 5, 1, 4 they give `[1, 4, 5]` on JDK 27. And `pq.stream().sorted(pq.comparator())` throws `NullPointerException` when the queue has no comparator. - If you frequently need *both* fast min-access and sorted iteration, a `TreeSet`/`TreeMap` (red-black tree) gives O(log n) ops *and* in-order iteration - but it forbids duplicates, unlike a heap. ## Why the design is this way Keeping the array fully sorted on every insert would make `offer` O(n). The heap keeps `offer`/`poll` at O(log n) by only enforcing the weaker parent-child invariant - a deliberate trade that sacrifices iteration order for cheap insertion and extraction.

  • How can you read a PriorityQueue in sorted order without emptying it?
    Copy it first: poll a new PriorityQueue<>(pq), which keeps the comparator, or sort new ArrayList<>(pq) with pq.comparator(). pq.stream().sorted() also leaves the original intact, but it uses natural ordering, so its order is wrong for a max-heap.
  • Is [1, 3, 2] a valid min-heap array?
    Yes. Root 1 has children 3 and 2; 1<=3 and 1<=2 both hold. Siblings 3 and 2 need not be ordered, so the array isn't sorted but the heap property holds.

  • Assuming for-each or toString prints elements sorted
  • Believing the iterator follows priority order
  • Thinking the whole backing array is sorted, not just the root
  • Polling the live queue when you needed to keep it intact

context