Contents
- Heap Property
- Key Operations and Complexity
- Java PriorityQueue API
- Min-Heap Example — Top K elements
- Max-Heap with Custom Comparator
- When to Use a Heap
- Min-Heap — root is the smallest; every parent ≤ its children. Peek gives min in O(1).
- Max-Heap — root is the largest; every parent ≥ its children. Peek gives max in O(1).
- Heaps are stored as arrays: for node at index i, left child at 2i+1, right at 2i+2, parent at (i-1)/2.
| Operation | Time | Description |
|---|
| offer / add | O(log n) | Insert element, sift up |
| poll / remove | O(log n) | Remove root, sift down |
| peek | O(1) | View root without removing |
| contains | O(n) | Linear scan (no direct structure) |
| Build heap (heapify) | O(n) | Build from existing array |
Java's PriorityQueue<T> is a min-heap by default. Use a custom Comparator
to get a max-heap or to heap by a field of a custom object.
import java.util.PriorityQueue;
import java.util.Collections;
// Min-Heap (default) — smallest element at the top
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
System.out.println(minHeap.peek()); // 1 (minimum)
System.out.println(minHeap.poll()); // 1 (removes and returns min)
// Max-Heap — largest element at the top
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// or: new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);
System.out.println(maxHeap.peek()); // 5 (maximum)
// Heap of custom objects — sorted by a field
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{3, "c"});
pq.offer(new int[]{1, "a"});
pq.offer(new int[]{2, "b"});
int[] min = pq.poll(); // {1, "a"}
A common pattern: maintain a min-heap of size k to efficiently track the top-K largest elements.
If the heap exceeds size k, remove the minimum (the smallest of the top-K).
// Find top-K largest elements using a min-heap of size k
public int[] topKLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // min at top
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // remove the smallest among top-k
}
}
// minHeap now contains the k largest elements
return minHeap.stream().mapToInt(Integer::intValue).toArray();
}
A min-heap of size k is the most memory-efficient way to find top-k largest elements.
Each insertion is O(log k), making the total time O(n log k) — much better than sorting O(n log n)
when k is small.
// Heap of tasks sorted by priority (highest priority first)
record Task(String name, int priority) {}
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
Comparator.comparingInt(Task::priority).reversed()
);
taskQueue.offer(new Task("Email", 1));
taskQueue.offer(new Task("Deploy", 10));
taskQueue.offer(new Task("Meeting", 5));
while (!taskQueue.isEmpty()) {
System.out.println(taskQueue.poll().name());
}
// Output: Deploy, Meeting, Email (priority descending)
- Top-K / Bottom-K problems — find the k largest or smallest elements efficiently.
- Running median — maintain two heaps (max-heap for lower half, min-heap for upper half).
- Merge K sorted lists/arrays — always pick the current minimum from K candidates.
- Dijkstra's / Prim's algorithms — always expand the nearest unvisited node.
- Scheduling / simulation — process events in priority order.