DSA Patterns Made Simple · Heaps, Backtracking and Dynamic Programming
Heaps: Top K and Always-the-Smallest
A heap hands you the smallest (or largest) item instantly and keeps that true as items come and go. Use it for the k largest, the k most frequent, merging sorted lists and running medians.
The problem
Kth Largest Element: in [3, 2, 1, 5, 6, 4], what's the 2nd largest number? Sorting works (O(n log n)), but if you only need the top k of a million numbers, sorting all million is wasted effort.
How to spot it
- "k largest / smallest / most frequent / closest"
- "Kth largest"
- Repeatedly take the smallest or largest item as new ones arrive (task scheduling, merging k sorted lists)
- A stream of numbers: running median, top k so far
The idea
A heap is like a hospital waiting room ordered by urgency: whoever is most urgent is always at the front, no matter what order people arrived in. Getting the front item, adding someone, or removing the front each costs O(log n).
Top k largest trick: keep a min-heap of size k. Push each number; if the heap grows past k, pop the smallest. The heap ends up holding the k largest, and its top is the kth largest. Cost: O(n log k), much better than sorting when k is small.
Python's heapq is a min-heap on a plain list. JavaScript has no built-in heap, so the example includes a small one (about 25 lines worth knowing; in interviews you can usually say "assume a heap class" and describe it).
The template
import heapq
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest; the k largest remain
kth_largest = heap[0]
const heap = new MinHeap(); // see the worked example for the class
for (const x of nums) {
heap.push(x);
if (heap.size > k) heap.pop(); // drop the smallest; the k largest remain
}
const kthLargest = heap.peek();
For a max-heap in Python, push negated values (-x). For "most frequent", push (count, item) pairs.
Worked example
Kth largest with a size-k heap, and the k most frequent words by pushing (count, word) pairs.
import heapq
from collections import Counter
def kth_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
def top_k_frequent(words, k):
counts = Counter(words)
heap = []
for word, count in counts.items():
heapq.heappush(heap, (count, word))
if len(heap) > k:
heapq.heappop(heap)
return [word for count, word in sorted(heap, reverse=True)]
print("2nd largest:", kth_largest([3, 2, 1, 5, 6, 4], 2))
print("4th largest:", kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))
words = "the day the sun shone the sun was warm and the day was long".split()
print("top 3 words:", top_k_frequent(words, 3))
Output
2nd largest: 5 4th largest: 4 top 3 words: ['the', 'was', 'sun']
class MinHeap {
constructor() { this.items = []; }
get size() { return this.items.length; }
peek() { return this.items[0]; }
less(a, b) { // compares numbers, or [count, word] pairs like Python tuples
if (Array.isArray(a)) return a[0] !== b[0] ? a[0] < b[0] : a[1] < b[1];
return a < b;
}
push(x) {
const h = this.items;
h.push(x);
for (let i = h.length - 1; i > 0;) { // bubble up
const parent = (i - 1) >> 1;
if (!this.less(h[i], h[parent])) break;
[h[i], h[parent]] = [h[parent], h[i]];
i = parent;
}
}
pop() {
const h = this.items, top = h[0], last = h.pop();
if (h.length) {
h[0] = last;
for (let i = 0; ;) { // sink down
const l = 2 * i + 1, r = l + 1;
let small = i;
if (l < h.length && this.less(h[l], h[small])) small = l;
if (r < h.length && this.less(h[r], h[small])) small = r;
if (small === i) break;
[h[i], h[small]] = [h[small], h[i]];
i = small;
}
}
return top;
}
}
function kthLargest(nums, k) {
const heap = new MinHeap();
for (const x of nums) {
heap.push(x);
if (heap.size > k) heap.pop();
}
return heap.peek();
}
function topKFrequent(words, k) {
const counts = new Map();
for (const w of words) counts.set(w, (counts.get(w) ?? 0) + 1);
const heap = new MinHeap();
for (const [word, count] of counts) {
heap.push([count, word]);
if (heap.size > k) heap.pop();
}
const kept = [];
while (heap.size) kept.push(heap.pop());
return kept.reverse().map(([, word]) => word);
}
console.log("2nd largest:", kthLargest([3, 2, 1, 5, 6, 4], 2));
console.log("4th largest:", kthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4));
const words = "the day the sun shone the sun was warm and the day was long".split(" ");
console.log("top 3 words:", "[" + topKFrequent(words, 3).map((w) => `'${w}'`).join(", ") + "]");
Output
2nd largest: 5 4th largest: 4 top 3 words: ['the', 'was', 'sun']
Ties (here "day", "sun" and "was" all appear twice) are broken by the word itself, because pairs compare item by item; the JavaScript less does the same.
Common mistakes
- Using a max-heap of everything for top k: O(n log n) and O(n) memory. A min-heap of size k is O(n log k) and O(k).
- Forgetting Python's heap is a min-heap. Negate values for max-heap behaviour.
- Reading
heap[0]as "the largest". In a min-heap it's the smallest of what you kept, which is exactly the kth largest. - Sorting a JavaScript array as a "heap" on every insert: O(n log n) each time.
Practice
- Kth Largest Element in an Array (medium)
- Top K Frequent Elements (medium): count first, then a size-k heap of (count, number).
Key points
- Heap = instant access to the smallest (or largest); push and pop are O(log n).
- Top k largest: min-heap capped at size k. O(n log k).
- Push
(priority, item)pairs to order by something other than the item. - Python:
heapq(min-heap). JavaScript: write or assume a small heap class.
Practice questions
Why does a min-heap of size k give the k largest elements?
Answer
Every time the heap exceeds k items, the smallest is removed. Anything popped is smaller than k other numbers, so it can't be in the top k; what remains are the k largest, with the kth largest on top.
What is the time complexity of finding the top k of n items with a heap?
Answer
O(n log k): each of the n pushes (and pops) works on a heap of at most k items. Space is O(k).
Open in the app to mark lessons complete, take notes and track your progress.