Java priority queues and heaps
Always remove the smallest (or largest) item, and find the k largest values.
import java.util.*;
class Main {
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int v : new int[] {5, 1, 8, 3, 9, 2}) {
minHeap.offer(v);
}
StringBuilder order = new StringBuilder();
while (!minHeap.isEmpty()) {
order.append(minHeap.poll()).append(' ');
}
System.out.println(order.toString().trim());
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.addAll(List.of(5, 1, 8, 3));
System.out.println("largest " + maxHeap.peek());
int k = 3;
PriorityQueue<Integer> top = new PriorityQueue<>();
for (int v : new int[] {7, 12, 3, 19, 5, 11, 2, 15}) {
top.offer(v);
if (top.size() > k) {
top.poll();
}
}
List<Integer> result = new ArrayList<>(top);
Collections.sort(result, Collections.reverseOrder());
System.out.println("top " + k + ": " + result);
}
}1 2 3 5 8 9 largest 8 top 3: [19, 15, 12]
Explanation
A priority queue gives quick access to the item with the highest priority. Java's PriorityQueue is a binary min-heap: poll removes the smallest element in O(log n), and offer adds one in O(log n). Peeking at the smallest element is O(1). A heap is stored in an array, where the children of position i are at 2i + 1 and 2i + 2.
A reversed comparator turns it into a max-heap. To find the k largest values of a long stream, keep a min-heap of size k. For each new value, add it, and if the heap grows beyond k, remove the smallest. At the end the heap contains the k largest values, and the work is O(n log k), which is better than sorting all n values.
Explore the dry run
import java.util.*; class Main { public static void main(String[] args) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int v : new int[] {5, 1, 8, 3, 9, 2}) { minHeap.offer(v); } StringBuilder order = new StringBuilder(); while (!minHeap.isEmpty()) { order.append(minHeap.poll()).append(' '); } System.out.println(order.toString().trim()); PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); maxHeap.addAll(List.of(5, 1, 8, 3)); System.out.println("largest " + maxHeap.peek()); int k = 3; PriorityQueue<Integer> top = new PriorityQueue<>(); for (int v : new int[] {7, 12, 3, 19, 5, 11, 2, 15}) { top.offer(v); if (top.size() > k) { top.poll(); } } List<Integer> result = new ArrayList<>(top); Collections.sort(result, Collections.reverseOrder()); System.out.println("top " + k + ": " + result); }}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| The default order makes a min-heap. | — | — | |
| poll always removes the current smallest, so the values come out sorted. | — | — | |
| Heap sort in miniature: n polls in sorted order. | — | 1 2 3 5 8 9 | |
| A reversed comparator puts the largest value at the top. | — | 1 2 3 5 8 9 | |
| peek looks at the top without removing it. | — | 1 2 3 5 8 9 largest 8 | |
| When the heap exceeds k items, drop the smallest, which cannot be among the k largest. | — | 1 2 3 5 8 9 largest 8 | |
| The heap kept 12, 15, and 19. | — | 1 2 3 5 8 9 largest 8 top 3: [19, 15, 12] |
Cost and common mistakes
offer and poll O(log n), peek O(1); the top-k method is O(n log k).
- Iterating over a PriorityQueue does not give sorted order. Only poll returns elements in priority order.
- PriorityQueue does not support fast removal of an arbitrary element or updating a priority in place.
- Null elements are not allowed, and elements must be comparable or come with a Comparator.
Try it yourself
What does poll() return when the queue is empty?
Reveal answer and reasoning
null. Unlike remove(), which throws NoSuchElementException, poll returns null for an empty queue.