PriorityQueue Example in Java
Problem
A PriorityQueue is backed by a heap, so it never keeps elements in insertion order — poll() always returns the smallest element remaining, according to natural ordering or a supplied Comparator.
Add several integers to a PriorityQueue in no particular order, then poll them back out one at a time.
Java Program
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(4);
pq.add(2);
pq.add(3);
while (!pq.isEmpty()) {
System.out.println(pq.poll()); // always removes the current smallest
}
}
}Output
Core Logic
Adding elements in arbitrary order still leaves the smallest one at the head of the heap, so repeatedly polling drains the queue in ascending order regardless of the order they went in.
- 1
new PriorityQueue<Integer>()creates an empty queue ordered by natural ordering — ascending for Integer. - 2
add(5), add(1), add(4), add(2), add(3)inserts the five values in a deliberately scrambled order. - 3Each
add()call re-heapifies just enough to keep the smallest element at the head — internally, the values are never stored in insertion order at all. - 4The
while (!pq.isEmpty())loop callspoll()repeatedly, each call removing and returning the current smallest element.
5 was added first, the first call to poll() returns 1 — the smallest value present — not the first one inserted.Key Point: A PriorityQueue's iteration order (and even its internal array order) is NOT sorted — only repeatedly calling poll() is guaranteed to produce elements in ascending order, one at a time.
Why: Both add() and poll() have to restore the heap property by sifting an element up or down the tree, which takes O(log n) per call, while the queue itself holds up to n elements at once.