Notes › DSA
Heaps and Priority Queue
A heap is a complete binary tree where every parent is smaller than its children (min-heap) or larger than them (max-heap). So the minimum (or maximum) is always at the root.
A priority queue is the abstract idea — "always give me the most important item" — and a heap is how it is usually built.
Stored in an array
A complete tree fits in an array with no pointers. For index i (0-based):
- parent =
(i − 1) / 2 - left child =
2i + 1, right child =2i + 2
min-heap: 1
/ \
3 5 array: [1, 3, 5, 7, 4, 8]
/ \ /
7 4 8
Operations
| Operation | How | Time |
|---|---|---|
| Peek min/max | a[0] |
O(1) |
| Insert | add at the end, sift up while smaller than the parent | O(log n) |
| Remove min/max | move the last element to the root, sift down | O(log n) |
| Build heap from n items | sift down from the last parent to the root | O(n) |
void siftDown(vector<int>& h, int i) { // min-heap
int n = h.size();
while (true) {
int smallest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && h[l] < h[smallest]) smallest = l;
if (r < n && h[r] < h[smallest]) smallest = r;
if (smallest == i) break;
swap(h[i], h[smallest]);
i = smallest;
}
}
C++ priority_queue
priority_queue<int> maxHeap; // largest on top
priority_queue<int, vector<int>, greater<int>> minHeap; // smallest on top
maxHeap.push(5); maxHeap.push(9);
cout << maxHeap.top(); // 9
maxHeap.pop();
// pairs: ordered by first, then second
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; // (distance, node) for Dijkstra
Java: PriorityQueue<Integer> is a min-heap by default; new PriorityQueue<>(Collections.reverseOrder()) for max. Python: heapq (min-heap; push -x for max).
Pattern 1: top K elements
K largest elements — keep a min-heap of size K; if it grows past K, pop the smallest. What remains are the K largest. Time O(n log K), better than sorting when K is small.
int kthLargest(vector<int>& a, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : a) {
pq.push(x);
if (pq.size() > k) pq.pop();
}
return pq.top();
}
Same idea: top K frequent elements, K closest points to the origin.
Pattern 2: merge K sorted lists/arrays
Push the first element of each list; pop the smallest, push its next. O(N log K) for N total elements.
Pattern 3: running median
Two heaps: a max-heap for the smaller half and a min-heap for the larger half, kept balanced (sizes differ by ≤ 1). The median is at the top(s). Each insert O(log n).
Pattern 4: greedy scheduling
- Task scheduler / meeting rooms II: min-heap of end times.
- Connect ropes with minimum cost: always join the two smallest (min-heap).
- Dijkstra's shortest path: min-heap of
(distance, node).
Heap sort
Build a max-heap, then repeatedly swap the root with the last element and sift down. O(n log n), O(1) space, not stable.
Classic problems
| Problem | Heap |
|---|---|
| Kth largest element | min-heap of size K |
| Top K frequent elements | count + min-heap |
| K closest points to origin | max-heap of size K |
| Merge K sorted lists | min-heap |
| Find median from data stream | two heaps |
| Last stone weight | max-heap |
| Minimum cost to connect ropes | min-heap |
| Task scheduler | max-heap of counts |
Practise in the Heap & Priority Queue section.
Interview one-liners
- A heap is not sorted — only the root is guaranteed to be the min/max.
- Building a heap is O(n), not O(n log n) (most nodes are near the bottom and sift down only a little).
- Search for an arbitrary value in a heap is O(n).
- "K largest" → min-heap of size K; "K smallest" → max-heap of size K.