Heap / Priority Queue - Introduction
A Heap is a complete binary tree that satisfies the heap property: in a min-heap every parent is smaller than or equal to its children; in a max-heap every parent is larger. This guarantees O(log n) insert and O(log n) removal of the minimum/maximum element, making heaps the go-to data structure for problems that repeatedly need the next smallest or largest element.
Contents
Heap Property
- 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
i2i+12i+2(i-1)/2
Key Operations and Complexity
| 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 PriorityQueue API
Java's PriorityQueue<T>Comparator
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"}Min-Heap Example: Top K elements
A common pattern: maintain a min-heap of size kk
// 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();
}Max-Heap with Custom Comparator
The class below shows the implementation. Key points are highlighted in the inline comments.
// 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)When to Use a Heap
- 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.