Brewlearn Get the app
🗃️ Collections Framework · Intermediate

PriorityQueue in Java

Binary heap ordered by priority; iteration order is not sorted.

🧩 The mysteryYou add 5, 1, 3 to a PriorityQueue and print it: [1, 5, 3]. Not sorted! Is it broken? No, and the reason is a beautiful data structure.

Hospital triage

A **PriorityQueue is like an ER triage desk: whoever has the highest priority goes next, not whoever arrived first. Here that means poll() and peek() always give the smallest element**, by natural order or a Comparator.

🔮 Predict it

Your turn

What does this print?

var pq = new PriorityQueue<Integer>();
pq.add(4);
pq.add(9);
pq.add(2);
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");
}
  1. 4 9 2
  2. 2 4 9
  3. 9 4 2
Show the answer

Each poll() removes the current minimum, so polling until empty gives ascending order: 2, 4, 9.

Inside: a binary heap

It's a binary heap stored in an array: a tree where every parent ≤ its children. The root is always the minimum, but siblings are in no particular order. So **peek is O(1); offer and poll are O(log n)**, because one element sifts up or down the tree's height.

//        2         array: [2, 9, 4]
//       / \
//      9   4
🔮 Predict it

Print it

Same three adds. What does println(pq) show?

var pq = new PriorityQueue<Integer>();
pq.add(4);
pq.add(9);
pq.add(2);
System.out.println(pq);
  1. [2, 4, 9]
  2. [2, 9, 4]
  3. [4, 9, 2]
Show the answer

toString shows the heap's internal array. 4 goes in, 9 becomes its child, then 2 is added as a child of 4 and bubbles up past it to the root: [2, 9, 4]. Only the head is guaranteed to be the minimum.

⚠️ The trap

Iterating isn't sorting

for-each, toString and streams over a PriorityQueue follow the heap layout, not sorted order. Need everything sorted? poll() repeatedly, or copy the elements and sort the copy.

for (int x : pq) { }  // ✗ heap order
while (!pq.isEmpty()) {
    use(pq.poll());   // ✓ smallest first
}

Flip it into a max-heap

Pass a comparator to change what "smallest" means. **Comparator.reverseOrder() flips natural order, so the largest** value sits at the head.

var max = new PriorityQueue<Integer>(
        Comparator.reverseOrder());
max.add(3); max.add(8); max.add(5);
max.peek();  // 8
💼 In the real world

Where heaps shine

Task schedulers (run the job with the earliest deadline), Dijkstra's shortest-path algorithm, merging sorted files, and the classic interview problem "find the top-k items" using a heap that never holds more than k elements.

Key takeaways

  1. poll() / peek() give the smallest element
  2. offer and poll: O(log n); peek: O(1)
  3. Iteration and toString follow the heap's array layout, not sorted order
  4. Max-heap: new PriorityQueue<>(Comparator.reverseOrder())

💡 An emergency room: the most urgent patient is always seen next, but the waiting room isn't lined up in order.

🤯 Did you know?

The binary heap was invented by J. W. J. Williams in 1964 as part of the heapsort algorithm. Java's PriorityQueue still uses the same idea, sixty years later.

Practice questions

What does this print?

var pq = new PriorityQueue<Integer>();
pq.add(5);
pq.add(1);
pq.add(3);
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");
}
  1. 5 1 3
  2. 1 3 5
  3. 5 3 1
  4. 1 5 3
Check your answer

1 3 5. Each poll() removes the current minimum, so polling until empty yields ascending order.

Make this a max-heap (largest first).

Queue<Integer> pq =
    new PriorityQueue<>(___);
  1. Comparator.reverseOrder()
  2. Integer::compare
  3. Collections.reverse()
  4. true
Check your answer

Comparator.reverseOrder(). Comparator.reverseOrder() flips natural ordering, so the largest Integer is treated as the 'smallest' and sits at the head. Integer::compare is the normal ascending order.

Next: Vector, Stack and Hashtable. They still compile in Java 25. So why does modern code avoid them?