How does PriorityQueue order its elements in Java?
PriorityQueue is a binary min-heap, so poll() always returns the smallest element by natural order or a Comparator. Add and poll cost O(log n), peek is O(1), and iterating it does not give sorted order.
Explain it simply
Think of a hospital emergency desk. The most serious patient is always seen first, whatever the arrival time. The rest of the waiting room is not neatly sorted, it just guarantees that the most urgent one is at the front.
Example
import java.util.*;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(30); pq.add(10); pq.add(20);
System.out.println(pq.peek()); // prints: 10
System.out.println(pq.poll()); // prints: 10
System.out.println(pq.poll()); // prints: 20
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(5); maxHeap.add(9); maxHeap.add(1);
System.out.println(maxHeap.poll()); // prints: 9What to say in the interview
"It is an array-based binary heap. By default it is a min-heap, and I pass Comparator.reverseOrder() for a max-heap. offer and poll are O(log n), peek is O(1), and contains or remove of an arbitrary item is O(n). Printing the queue or iterating over it shows heap order, not sorted order, so to get sorted output I must poll repeatedly. It does not accept null and is not thread-safe."
Common mistakes
- Printing a PriorityQueue and assuming the output is sorted.
- Using it with elements that are not Comparable and giving no Comparator, which throws ClassCastException.