Why is iterating over a PriorityQueue not the same as getting elements in sorted order?
answer
- Heap = partially ordered array, not sorted
- Only the head (index 0) is guaranteed min
- Iterator/for-each/toString walk raw array order
- poll() in a loop = the only sorted read
- Sort a copy if you must keep the queue
basics
~10 sIterating (for-each, iterator, toArray, toString) walks the internal heap array, which is only partially ordered - just the head is guaranteed smallest. Only repeatedly calling poll() gives elements in true sorted order.
solid answer
~50 sA 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. The *only* way to read elements in priority order is to drain the queue with poll() (or remove()) in a loop, which removes the head and re-heapifies each time. If you need to iterate sorted without destroying the queue, copy it and poll the copy, or use a TreeSet/sorted stream instead.
go deeper
Knows iterating doesn't print sorted order and that poll() is the way to get sorted output.
Explains the heap is a partially ordered array where only the root is guaranteed minimum, and names which operations (iterator/toString/stream) ignore order.
Ties it to the heap property and sift-down, explains the O(log n) trade-off, and gives non-destructive sorted-read workarounds.
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 The `iterator()`, enhanced `for`, `toArray()`, `stream()`, and `toString()` all walk that backing array **in array index order**. Because the array is only heap-ordered, you get an order that starts with the minimum but is otherwise arbitrary. The Javadoc states plainly: *"The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order."* ## The one way to get sorted output The ordering guarantee lives only in `poll()` / `remove()`. Each `poll()`: 1. takes the root (current minimum), 2. moves the last array element to the root, and 3. **sift-downs** it (swaps it with its smaller child repeatedly) 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: `new ArrayList<>(pq)` then `Collections.sort(...)`, or poll a **copy** (`new PriorityQueue<>(pq)`), or `pq.stream().sorted()`. - 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 - e.g. new PriorityQueue<>(pq) or new ArrayList<>(pq) sorted - and drain/sort the copy, or use pq.stream().sorted(). The original stays intact.
- 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.
saying these in an interview costs you the question
- 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