Contents
- Heap Basics & Internal Structure
- Min-Heap — Natural Ordering
- Max-Heap — Reversed Comparator
- Custom Object Priority
- Core API — offer, poll, peek, remove
- Time Complexity
- Common Patterns
- Pitfalls & Limitations
Java's PriorityQueue is backed by a binary min-heap: an array where the smallest element is always at index 0, and every parent is smaller than or equal to its children. Insertion adds the new element at the end of the array then "sifts up" — swapping with its parent until the heap property is restored. Removal takes the root (minimum), replaces it with the last element, then "sifts down". Both operations are O(log n) because a complete binary tree of n nodes has height log₂ n.
// Conceptual heap array representation
// Tree: 1
// / \
// 3 5
// / \ / \
// 7 9 8 6
//
// Array: [1, 3, 5, 7, 9, 8, 6]
// 0 1 2 3 4 5 6
//
// Parent of index i: (i - 1) / 2
// Left child of i: 2 * i + 1
// Right child of i: 2 * i + 2
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
pq.offer(7);
pq.offer(2);
// peek() = root of heap = minimum element, O(1)
System.out.println(pq.peek()); // 1
// Iterating does NOT give sorted order — heap is not fully sorted
System.out.println(pq); // [1, 2, 3, 7, 5] — heap-ordered, not sorted
// poll() removes and returns the minimum, then restores heap — O(log n)
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " "); // 1 2 3 5 7 — ascending order
}
Iterating a PriorityQueue with a for-each loop or iterator() does not yield elements in priority order. Only repeated poll() calls drain the queue in order. This is a very common source of bugs.
By default, PriorityQueue uses the natural ordering of elements (via Comparable), making it a min-heap: poll() always returns the smallest element. For numbers this means ascending order; for strings, lexicographic order.
import java.util.*;
// Integer min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
int[] values = {10, 4, 7, 1, 9, 3, 8, 2, 6, 5};
for (int v : values) minHeap.offer(v);
System.out.println("Sorted ascending:");
while (!minHeap.isEmpty()) {
System.out.print(minHeap.poll() + " ");
}
// 1 2 3 4 5 6 7 8 9 10
// String min-heap — lexicographic order
PriorityQueue<String> words = new PriorityQueue<>();
words.addAll(List.of("banana", "apple", "cherry", "date", "elderberry"));
while (!words.isEmpty()) {
System.out.print(words.poll() + " ");
}
// apple banana cherry date elderberry
There is no built-in MaxPriorityQueue in Java. To get a max-heap, pass Comparator.reverseOrder() to the constructor. poll() then always returns the largest element.
import java.util.*;
// Integer max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
for (int v : new int[]{10, 4, 7, 1, 9, 3}) maxHeap.offer(v);
System.out.println("Sorted descending:");
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " ");
}
// 10 9 7 4 3 1
// Alternative: negate the comparison lambda
PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>((a, b) -> b - a);
// Warning: b - a can overflow for extreme values; prefer Integer.compare(b, a)
PriorityQueue<Integer> maxHeap3 = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
// String max-heap — reverse lexicographic
PriorityQueue<String> revWords = new PriorityQueue<>(Comparator.reverseOrder());
revWords.addAll(List.of("banana", "apple", "cherry", "date"));
while (!revWords.isEmpty()) System.out.print(revWords.poll() + " ");
// date cherry banana apple
For custom objects, supply a Comparator or implement Comparable. The comparator defines what "highest priority" means for your domain — lowest latency, highest urgency, earliest deadline, or any other criterion.
import java.util.*;
record Task(String name, int priority, java.time.Instant deadline) {}
// Min-heap by priority (1 = highest priority, 10 = lowest)
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
Comparator.comparingInt(Task::priority)
.thenComparing(Task::deadline) // tie-break by earliest deadline
);
taskQueue.offer(new Task("Send report", 3, java.time.Instant.parse("2025-04-20T09:00:00Z")));
taskQueue.offer(new Task("Fix bug", 1, java.time.Instant.parse("2025-04-18T10:00:00Z")));
taskQueue.offer(new Task("Code review", 2, java.time.Instant.parse("2025-04-18T14:00:00Z")));
taskQueue.offer(new Task("Deploy update", 1, java.time.Instant.parse("2025-04-19T08:00:00Z")));
taskQueue.offer(new Task("Write tests", 2, java.time.Instant.parse("2025-04-17T16:00:00Z")));
System.out.println("Tasks in priority order:");
while (!taskQueue.isEmpty()) {
Task t = taskQueue.poll();
System.out.printf(" [%d] %s (by %s)%n", t.priority(), t.name(), t.deadline());
}
// [1] Fix bug (by 2025-04-18T10:00:00Z)
// [1] Deploy update (by 2025-04-19T08:00:00Z)
// [2] Write tests (by 2025-04-17T16:00:00Z)
// [2] Code review (by 2025-04-18T14:00:00Z)
// [3] Send report (by 2025-04-20T09:00:00Z)
| Method | Description | On empty queue | Complexity |
|---|
| offer(e) / add(e) | Insert element | – | O(log n) |
| poll() | Remove & return head (min/max) | Returns null | O(log n) |
| remove() | Remove & return head | Throws NoSuchElementException | O(log n) |
| peek() | Return head without removing | Returns null | O(1) |
| element() | Return head without removing | Throws NoSuchElementException | O(1) |
| remove(o) | Remove specific element | Returns false | O(n) |
| contains(o) | Check if element present | – | O(n) |
| size() | Number of elements | – | O(1) |
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 2, 8, 1, 9));
System.out.println(pq.peek()); // 1 — head, not removed
System.out.println(pq.poll()); // 1 — head removed, heap restructured
System.out.println(pq.peek()); // 2 — new head
// Safe drain loop
while (!pq.isEmpty()) {
int head = pq.poll();
// process head
}
// Remove a specific element — O(n) linear scan
PriorityQueue<String> tasks = new PriorityQueue<>(List.of("A", "B", "C"));
tasks.remove("B"); // removes "B" specifically, not the head
System.out.println(tasks); // [A, C] in some order
// Convert to sorted array (draining)
PriorityQueue<Integer> copy = new PriorityQueue<>(List.of(3, 1, 4, 1, 5, 9));
int[] sorted = new int[copy.size()];
for (int i = 0; !copy.isEmpty(); i++) sorted[i] = copy.poll();
System.out.println(Arrays.toString(sorted)); // [1, 1, 3, 4, 5, 9]
| Operation | PriorityQueue (heap) | Sorted List | TreeSet |
|---|
| Insert | O(log n) | O(n) | O(log n) |
| Find min/max | O(1) | O(1) | O(log n) |
| Remove min/max | O(log n) | O(1) | O(log n) |
| Remove arbitrary | O(n) | O(n) | O(log n) |
| Contains | O(n) | O(log n)* | O(log n) |
| Build from n elements | O(n) | O(n log n) | O(n log n) |
* sorted list supports binary search; PriorityQueue does not
Use PriorityQueue when you repeatedly need the minimum (or maximum) element and the collection changes frequently. Use a sorted list or TreeSet when you need arbitrary access to any rank position, or when contains() / remove(arbitrary) are frequent operations.
Three patterns appear repeatedly in algorithm problems and production code:
import java.util.*;
// ── PATTERN 1: Top-K Smallest Elements ──────────────────────────────────────
// Keep a max-heap of size K. If a new element is smaller than the heap's max,
// replace the max. After processing all elements, the heap contains the K smallest.
public static List<Integer> topKSmallest(int[] nums, int k) {
// Max-heap of size k
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
for (int n : nums) {
maxHeap.offer(n);
if (maxHeap.size() > k) maxHeap.poll(); // evict the largest
}
List<Integer> result = new ArrayList<>(maxHeap);
Collections.sort(result);
return result;
}
System.out.println(topKSmallest(new int[]{7,2,9,1,4,8,3,6,5}, 3)); // [1, 2, 3]
// ── PATTERN 2: Top-K Largest Elements ───────────────────────────────────────
// Keep a min-heap of size K. Evict the smallest when size > K.
public static List<Integer> topKLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
minHeap.offer(n);
if (minHeap.size() > k) minHeap.poll(); // evict the smallest
}
List<Integer> result = new ArrayList<>(minHeap);
Collections.sort(result, Collections.reverseOrder());
return result;
}
System.out.println(topKLargest(new int[]{7,2,9,1,4,8,3,6,5}, 3)); // [9, 8, 7]
// ── PATTERN 3: Merge K Sorted Lists ─────────────────────────────────────────
// Place the head of each list into a min-heap with a pointer to its list.
// Repeatedly extract the minimum and advance the pointer for that list.
public static List<Integer> mergeKSorted(List<List<Integer>> lists) {
record Entry(int value, int listIndex, int elemIndex) {}
PriorityQueue<Entry> pq = new PriorityQueue<>(Comparator.comparingInt(Entry::value));
for (int i = 0; i < lists.size(); i++) {
if (!lists.get(i).isEmpty()) {
pq.offer(new Entry(lists.get(i).get(0), i, 0));
}
}
List<Integer> result = new ArrayList<>();
while (!pq.isEmpty()) {
Entry e = pq.poll();
result.add(e.value());
int nextIdx = e.elemIndex() + 1;
if (nextIdx < lists.get(e.listIndex()).size()) {
pq.offer(new Entry(lists.get(e.listIndex()).get(nextIdx), e.listIndex(), nextIdx));
}
}
return result;
}
System.out.println(mergeKSorted(List.of(
List.of(1, 4, 7),
List.of(2, 5, 8),
List.of(3, 6, 9)
)));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
- Iteration order is undefined. A for-each loop over a PriorityQueue does not yield elements in priority order. Only poll() does. If you need ordered iteration without removing, drain to a list: new ArrayList<>(pq) then sort, or use while (!pq.isEmpty()) pq.poll().
- No O(log n) decrease-key. Standard Java PriorityQueue has no efficient "update priority" operation. To re-prioritize an element you must remove it (O(n)) and re-insert (O(log n)). For Dijkstra's algorithm with many re-priorities, consider using a TreeMap or the lazy-deletion trick.
- Not thread-safe. Use java.util.concurrent.PriorityBlockingQueue for concurrent producer-consumer scenarios.
- null elements are forbidden. Inserting null throws NullPointerException because comparison requires a non-null key.
- Duplicates are allowed. Unlike TreeSet, PriorityQueue permits duplicate elements.
import java.util.*;
// Pitfall: iterating instead of polling
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(3, 1, 4, 1, 5));
// WRONG — not in priority order
System.out.println("Iteration: " + pq); // [1, 1, 4, 3, 5] — heap order, not sorted
// CORRECT — poll until empty
List<Integer> ordered = new ArrayList<>();
while (!pq.isEmpty()) ordered.add(pq.poll());
System.out.println("Polled: " + ordered); // [1, 1, 3, 4, 5]
// Thread-safe priority queue
java.util.concurrent.PriorityBlockingQueue<Integer> concurrent =
new java.util.concurrent.PriorityBlockingQueue<>();
concurrent.put(5);
concurrent.put(1);
concurrent.put(3);
System.out.println(concurrent.take()); // 1 — blocks if empty