PriorityQueue
IntermediateA min-heap by default — use it for always-accessible minimum (or maximum with a reversed Comparator), scheduling, and top-K problems.
Overview
PriorityQueue implements Queue using a binary min-heap: the smallest element (by natural order or Comparator) is always at the head. poll() removes and returns the minimum in O(log n). peek() returns the minimum without removing in O(1). offer()/add() inserts in O(log n). Iteration does NOT return elements in sorted order — only poll() gives them in order. PriorityQueue is the natural tool for Dijkstra's algorithm, merge-K-sorted-lists, top-K elements, and any greedy algorithm that repeatedly needs the current minimum.
Min-Heap & Max-Heap
Default PriorityQueue is a min-heap — the smallest element is polled first. To create a max-heap, pass Comparator.reverseOrder() at construction (for types with natural ordering) or write a custom Comparator.
The heap invariant: every parent node ≤ its children (min-heap). Internally, the heap is stored in an array where parent of index i is at (i-1)/2, left child at 2i+1, right child at 2i+2.
import java.util.PriorityQueue;
import java.util.Comparator;
public class PriorityQueueDemo {
public static void main(String[] args) {
// Min-heap (default) — smallest element polled first
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.offer(2);
minHeap.offer(4);
System.out.print("Min-heap poll order: ");
while (!minHeap.isEmpty()) {
System.out.print(minHeap.poll() + " "); // 1 2 3 4 5
}
System.out.println();
// Max-heap — largest element polled first
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(3);
maxHeap.offer(2); maxHeap.offer(4);
System.out.print("Max-heap poll order: ");
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " "); // 5 4 3 2 1
}
System.out.println();
// Custom object heap — sorted by priority field
record Task(String name, int priority) {}
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
Comparator.comparingInt(Task::priority));
taskQueue.offer(new Task("Low", 3));
taskQueue.offer(new Task("High", 1));
taskQueue.offer(new Task("Medium", 2));
while (!taskQueue.isEmpty()) {
Task t = taskQueue.poll();
System.out.println("Processing: " + t.name()); // High, Medium, Low
}
}
}Top-K Problems & Heap Patterns
The classic heap interview pattern: finding the Kth largest (or smallest) element in a stream without sorting the whole array.
Kth largest — maintain a min-heap of size K. For each element: if heap size < K, add it. Else if element > heap.peek(), remove the min and add the element. The answer is always heap.peek().
Kth smallest — maintain a max-heap of size K similarly.
Merge K sorted lists — use a min-heap of (value, listIndex, nodeIndex) tuples.
import java.util.PriorityQueue;
import java.util.Arrays;
public class HeapPatterns {
// Kth largest in an array — O(n log k)
static int kthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int n : nums) {
minHeap.offer(n);
if (minHeap.size() > k) minHeap.poll(); // remove smallest
}
return minHeap.peek(); // kth largest is now the min of the heap
}
// Top K frequent elements
static int[] topKFrequent(int[] nums, int k) {
java.util.Map<Integer, Integer> freq = new java.util.HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
// Min-heap by frequency — keep only top k
PriorityQueue<int[]> heap = new PriorityQueue<>(
Comparator.comparingInt(a -> a[1]));
for (var entry : freq.entrySet()) {
heap.offer(new int[]{entry.getKey(), entry.getValue()});
if (heap.size() > k) heap.poll();
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) result[i] = heap.poll()[0];
return result;
}
// Dijkstra's shortest path — classic PriorityQueue usage
static int[] dijkstra(int[][] graph, int src) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// Min-heap: [distance, node]
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, src});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
if (d > dist[u]) continue; // stale entry
for (int v = 0; v < n; v++) {
if (graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}
public static void main(String[] args) {
int[] nums = {3, 2, 1, 5, 6, 4};
System.out.println(kthLargest(nums, 2)); // 5
int[] top = topKFrequent(new int[]{1,1,1,2,2,3}, 2);
System.out.println(Arrays.toString(top)); // [1, 2]
}
}PriorityQueue API & Pitfalls
Key PriorityQueue methods: offer(E) / add(E) — insert, O(log n) poll() — remove + return min/max, O(log n); returns null if empty peek() — view min/max without removing, O(1); returns null if empty remove(Object) — remove specific element, O(n) linear search contains(Object) — O(n) size(), isEmpty() — O(1)
Pitfalls: • Iteration (for-each, toArray) does NOT return elements in priority order — only sequential poll() does • Not thread-safe — use PriorityBlockingQueue for concurrent use • Modifying a held element's comparison field after insertion corrupts the heap
import java.util.*;
public class PriorityQueueAPI {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));
// peek — O(1), does not remove
System.out.println(pq.peek()); // 1
// PITFALL: iteration is NOT in priority order
System.out.print("for-each (unordered): ");
for (int n : pq) System.out.print(n + " "); // heap array order, not sorted!
System.out.println();
// Correct way to drain in order
System.out.print("poll order: ");
while (!pq.isEmpty()) System.out.print(pq.poll() + " "); // 1 1 2 3 4 5 6 9
System.out.println();
// remove(Object) — O(n)
PriorityQueue<Integer> pq2 = new PriorityQueue<>(List.of(10, 20, 30));
pq2.remove(20); // removes first occurrence of 20
System.out.println(pq2); // [10, 30]
// Initial capacity hint
PriorityQueue<Integer> large = new PriorityQueue<>(1000);
// Pre-allocates array for 1000 elements — avoids resizing
// Convert sorted stream to sorted list using heap
PriorityQueue<String> strPQ = new PriorityQueue<>(
List.of("banana", "apple", "cherry"));
List<String> sorted = new ArrayList<>();
while (!strPQ.isEmpty()) sorted.add(strPQ.poll());
System.out.println(sorted); // [apple, banana, cherry]
}
}Interactive Visualization
Key Points to Remember
- PriorityQueue is a min-heap by default — poll() always returns the smallest element
- For max-heap: new PriorityQueue<>(Comparator.reverseOrder())
- offer/add: O(log n); poll/remove head: O(log n); peek: O(1); contains/remove(obj): O(n)
- Iterating a PriorityQueue does NOT yield elements in sorted order — only sequential poll() does
- Kth largest: maintain a min-heap of size K — peek() is always the Kth largest
- PriorityQueue is not thread-safe — use PriorityBlockingQueue for concurrent use
Practice PriorityQueue in the Playground
Run and modify code directly in your browser - no setup needed.
Interview Questions
Sign in to ask AriaWhat is the internal data structure of PriorityQueue?
How do you create a max-heap using PriorityQueue?
Find the Kth largest element in an array using a heap
What is the time complexity of offer() and poll() in PriorityQueue?
How does Dijkstra's algorithm use a PriorityQueue?
Ask Aria about PriorityQueue
Your personal AI tutor — ask anything about this concept