Why doesn't printing a PriorityQueue show the elements in order?

The Answer

• A PriorityQueue is a binary heap stored in an array, not a sorted list.
• The heap invariant is only about parents and children: every parent compares ≤ both of its children. Siblings are unordered, and so is everything else.
• That invariant is enough to put the minimum at index 0 — which is all peek() and poll() need, and all they promise.
• toString() and iteration walk the backing array, so they show heap order. The iterator's order is explicitly unspecified.
• Keeping it fully sorted would cost more for no benefit: add and poll are O(log n) on a heap, and sorting would make add O(n).
• Ties are not stable. Equal priorities come out in no defined order — add a tiebreaker if you need one.

Understand It

The invariant is weaker than "sorted", on purpose

Sorted means every element is in the right place relative to every other element. A heap promises much less:

for every index i:
    heap[i] <= heap[2i + 1]     # its left child
    heap[i] <= heap[2i + 2]     # its right child

No relationship is claimed between siblings, between cousins, or between an element and its uncle. The only thing that follows globally is that heap[0] is the minimum — because it is ≤ its children, which are ≤ theirs, all the way down.

That is the whole trick. A queue that only ever hands you the smallest element does not need to know the order of the rest, and refusing to compute it is why add is O(log n) instead of O(n).

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 9, 3, 7, 2));

System.out.println("toString  : " + pq);
System.out.print("iteration : ");
for (int v : pq) System.out.print(v + " ");
System.out.println();

System.out.print("poll order: ");
PriorityQueue<Integer> copy = new PriorityQueue<>(pq);
while (!copy.isEmpty()) System.out.print(copy.poll() + " ");
System.out.println();
System.out.println("peek      : " + pq.peek());

toString  : [1, 3, 2, 5, 7, 9]
iteration : 1 3 2 5 7 9 
poll order: 1 2 3 5 7 9 
peek      : 1

[1, 3, 2, 5, 7, 9] is not sorted — 3 sits before 2 — and it satisfies the invariant perfectly. Check it: index 0 is 1, children at 1 and 2 are 3 and 2, both larger. Index 1 is 3, children at 3 and 4 are 5 and 7, both larger. Index 2 is 2, child at 5 is 9. Every parent beats its children, and nothing else is promised.

Poll the same queue and you get 1 2 3 5 7 9, because each poll re-heapifies and surfaces the next minimum.

Watching the heap assemble itself

Adding an element puts it at the end of the array and sifts it up while it beats its parent:

add(x):
    heap[size] ← x                       # first free slot
    i ← size; size ← size + 1
    while i > 0:                         # sift up
        parent ← (i - 1) / 2
        if heap[i] >= heap[parent]: stop  # invariant holds, done
        swap(heap[i], heap[parent])
        i ← parent
                                         # at most log₂(n) swaps

PriorityQueue<Integer> step = new PriorityQueue<>();
for (int v : new int[] {5, 1, 9, 3, 7, 2}) {
    step.add(v);
    System.out.println("add " + v + " -> " + step);
}

add 5 -> [5]
add 1 -> [1, 5]
add 9 -> [1, 5, 9]
add 3 -> [1, 3, 9, 5]
add 7 -> [1, 3, 9, 5, 7]
add 2 -> [1, 3, 2, 5, 7, 9]

Follow add 3. It lands at index 3, whose parent is index 1 holding 5. Three beats five, so they swap — giving [1, 3, 9, 5]. Its new parent is index 0 holding 1, which it does not beat, so it stops. One swap, and the array is never sorted at any point.

poll is the mirror image: take heap[0], move the last element into the hole and sift down, swapping with the smaller child until the invariant holds again. Also O(log n).

Ties are not stable

This is the part that causes real bugs, because "priority queue" sounds like it should behave like a queue for equal priorities:

record Task(String name, int priority) {}

PriorityQueue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
for (String n : new String[] {"a", "b", "c", "d", "e"}) tasks.add(new Task(n, 1));

System.out.print("all priority 1, polled in order: ");
while (!tasks.isEmpty()) System.out.print(tasks.poll().name() + " ");
System.out.println();

all priority 1, polled in order: a e d c b 

Five tasks, identical priority, inserted a-b-c-d-e, and they come out a e d c b. Nothing is wrong — the comparator says they are all equal, so any order satisfies it. The sift operations simply moved them around.

If insertion order matters among equals, put it in the comparator:

record Task(String name, int priority, long seq) {}

Comparator<Task> fifoWithinPriority = Comparator
        .comparingInt(Task::priority)
        .thenComparingLong(Task::seq);      // a monotonic counter you assign

What the contract actually covers

The two O(n) rows are the ones that surprise people. A heap has no index by value, so finding an arbitrary element means scanning the array — the same trap as List.contains, and just as easy to put inside a loop.

Reference

Getting sorted output, when that is what you actually wanted:

// Drain it — O(n log n), and destroys the queue
List<Integer> sorted = new ArrayList<>();
while (!pq.isEmpty()) sorted.add(pq.poll());

// Copy, then drain — keeps the original
PriorityQueue<Integer> copy = new PriorityQueue<>(pq);

// If you never needed a queue, do not use one
List<Integer> list = new ArrayList<>(values);
Collections.sort(list);            // one pass, and it stays sorted

// Sorted *and* navigable, if you need both ends and lookups
TreeSet<Integer> set = new TreeSet<>(values);   // O(log n) contains, no duplicates

Choosing the structure by what you need:

Max-heap, and the way to get it that does not break on MIN_VALUE:

// RIGHT
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// WRONG — negating a comparator's result breaks on Integer.MIN_VALUE
PriorityQueue<Integer> broken = new PriorityQueue<>((x, y) -> -(x - y));

Top-k, which is the reason to reach for a heap over a sort:

// k largest of n, in O(n log k) time and O(k) space — never sorts all n
PriorityQueue<Integer> kLargest = new PriorityQueue<>();   // min-heap of size k
for (int v : values) {
    kLargest.add(v);
    if (kLargest.size() > k) kLargest.poll();              // drop the smallest
}

Scenarios

A task scheduler that runs tasks out of order. Equal priorities, and the team assumed FIFO within a priority. It works in testing with three tasks and scrambles under load. Add a sequence number to the comparator; do not rely on the heap.

Dijkstra, and the "decrease key" problem. Textbook Dijkstra updates a node's distance while it sits in the queue. Java's PriorityQueue has no decreaseKey, and mutating an element in place does not re-heapify — the element keeps its old position and the invariant silently breaks. The standard workaround is to add the node again with the better distance and skip already-finalised nodes when polling.

Logging a queue's contents in a diagnostic. log.info("queue: {}", pq) prints heap order, and the next person to read that log concludes the priority logic is broken. Log new ArrayList<>(pq) sorted, or log only the head.

A "priority queue" that is polled once. If you add n items and poll one, you paid O(n log n) to build a structure you used once. A single linear scan for the minimum is O(n) and simpler.

Interviewer's Next Move

1. "Why not keep it sorted, so iteration works too?" Because insertion would become O(n) — you would have to shift elements to make room. The heap gives O(log n) insert and O(1) access to the minimum, which is exactly what a priority queue is for. Sorted order is extra work nobody asked for.

2. "Is poll() order guaranteed when priorities tie?" No. The comparator declares them equal, so any order is correct. PriorityQueue is documented as not stable. A sequence number in the comparator is the fix.

3. "What is the cost of remove(someElement)?" O(n) — a linear scan to find it, then O(log n) to restore the invariant. Only poll() is cheap, because only the head's position is known. This is why a heap is a poor choice when you need to cancel arbitrary entries.

4. "What happens if you mutate an element already in the queue?" Its position does not change, so the invariant can be violated and poll() may return the wrong element. Same class of bug as mutating a HashMap key: the structure filed it by a value that no longer holds. Remove, mutate, re-add.

5. "How would you find the k largest of a billion numbers?" A min-heap capped at k, polling whenever it exceeds k — O(n log k) time and O(k) memory, and it never holds more than k elements. Sorting all n would be O(n log n) and require all of it in memory at once.

Check Yourself

A PriorityQueue prints [1, 3, 2, 5]. Is it broken? No. The invariant only requires each parent to beat its children: 1 beats 3 and 2, and 3 beats 5. Siblings 3 and 2 are unordered, which is allowed. The minimum is still at index 0, which is the only position that is promised.

Why is peek() O(1) but contains() O(n)? Because the heap invariant identifies exactly one position — index 0 holds the minimum. It says nothing about where any other value lives, so finding an arbitrary element means examining the whole array.

Five items with identical priority are polled in a scrambled order. What is the fix? Make them not identical: add a monotonically increasing sequence number and compare on it after priority. The queue is behaving correctly — the comparator was under-specified.