When to Use a Heap (The Answer Interviewers Want to Hear)

Companion piece for the YouTube video. Snippets, in the order they appear on screen, the k-largest template, the kth-largest variation, and the top-k-frequent solution, plus a bonus at the end for the heapq basics I talked through but didn't put on screen. No extra commentary here beyond what you need to read the code. If you want the full walkthrough of the decisions behind each one, that's in the video.

k largest elements template

The skeleton to have memorized. Push every element; the moment the heap exceeds size k, pop the minimum. The heap never grows past k, so every push and pop is O(log k) and the whole pass is O(n log k). When the loop ends the heap holds exactly the k largest values, with the k-th largest sitting at the root -- so for LeetCode 215, "kth largest element," you return min_heap[0] instead of the whole list.

import heapq

def k_largest(nums, k):
    min_heap = []

    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    return list(min_heap)

Min heap for k largest, max heap for k smallest -- the element that should be evicted first when the heap is full is the one that sits on top. Python's heapq is a min heap only, so for max-heap behavior you negate values going in and negate again coming out.

top k frequent elements (LeetCode 347)

A heap problem with a frequency map bolted on. Count first, then run the same k-largest pattern on the counts. The heap stores (freq, num) tuples -- Python compares tuples element by element, so frequency ends up the sort key with no custom comparator.

import heapq
from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)

    min_heap = []
    for num, freq in count.items():
        heapq.heappush(min_heap, (freq, num))
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    return [num for freq, num in min_heap]

O(n log k) time, O(n) space for the counter plus O(k) for the heap. The same shape transfers to k closest points to origin (LeetCode 973), top k frequent words (LeetCode 692), and kth largest element in a stream (LeetCode 703).

Bonus: the heapq basics

I described this in the video but didn't show it. heapq operates on a plain list in place -- there's no heap type to construct. It only builds a min heap, so for a max heap you negate on the way in and negate again on the way out. heapify converts an existing list in O(n), which beats pushing n elements one at a time at O(n log n).

import heapq

# min heap
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)
smallest = heapq.heappop(min_heap)  # returns 1

# max heap: negate values
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -2)
largest = -heapq.heappop(max_heap)  # returns 3

# heapify an existing list in O(n)
nums = [3, 1, 4, 1, 5, 9]
heapq.heapify(nums)  # nums is now a valid min heap

heappush and heappop are both O(log n); heap[0] peeks at the minimum in O(1) without removing it.

Full breakdown of the three signals that say "this is a heap problem," the min-heap-for-k-largest logic, and the mistakes that cost candidates points, in the video. Next up in the series: dynamic programming.