Heaps and Top-K
On this page
A heap gives you the smallest (or largest) item in O(1) and lets you add or remove items in O(log n). That makes it the tool for "best so far" questions: the k largest values, the k closest points, the next event in time order, the median of a stream. You never sort everything, you only keep what can still matter.
Heaps covers how a heap works. Python's heapq is a min-heap; for a max-heap, push negated values.
When to recognise it
- "k largest / k smallest / k most frequent / k closest": a heap of size k.
- "Merge k sorted lists / arrays / streams": a heap holding the current head of each.
- "Median of a data stream", "sliding median": two heaps.
- Scheduling: "which task, room or machine frees up next?" A heap of end times (see Intervals).
- Shortest paths with weights (Dijkstra): a heap of (distance, node). See Graph BFS and DFS.
Pattern 1: top-k with a size-k heap
To find the k largest, keep a min-heap of size k. Its root is the smallest of the k biggest values seen so far, so anything smaller than the root cannot be in the top k. When the heap grows past k, pop the root.
![Reading [3, 2, 1, 5, 6, 4] with k = 3. The heap fills to [1, 2, 3], then each new value pushes out the smallest: 1, then 2, then 3. The final root 4 is the 3rd largest.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-e8e98c5c.png)
import heapq
def kth_largest(nums, k):
"""Min-heap of size k: the root is the smallest of the k biggest, i.e. the k-th largest."""
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # throw away the smallest
return heap[0]
Time O(n log k), space O(k). That beats sorting (O(n log n)) when k is small, and it works on a stream you cannot store.
For "top k frequent", count first and push (count, value) pairs:
import heapq
from collections import Counter
def top_k_frequent(nums, k):
"""Same idea with (count, value) pairs. Ties broken by value so the output is deterministic."""
heap = []
for val, cnt in Counter(nums).items():
heapq.heappush(heap, (cnt, -val))
if len(heap) > k:
heapq.heappop(heap)
return sorted((-v for c, v in heap))
Pattern 2: k-way merge
Each list is sorted, so the overall smallest item is one of the k current heads. Keep those heads in a heap, pop the smallest, and push the next item from the same list.
import heapq
def merge_k_sorted(lists):
"""K-way merge: the heap holds the current head of every list."""
heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
heapq.heapify(heap)
out = []
while heap:
val, i, j = heapq.heappop(heap)
out.append(val)
if j + 1 < len(lists[i]):
heapq.heappush(heap, (lists[i][j + 1], i, j + 1)) # i breaks ties
return out
Time O(N log k) for N total items. The list index i in the tuple breaks ties, so Python never has to compare two list nodes or objects.
Pattern 3: two heaps for a running median
Split the numbers into a low half (a max-heap) and a high half (a min-heap). The median sits at the tops.

import heapq
class RunningMedian:
"""Two heaps: max-heap for the low half (stored negated), min-heap for the high half."""
def __init__(self):
self.low, self.high = [], []
def add(self, x):
heapq.heappush(self.low, -x)
heapq.heappush(self.high, -heapq.heappop(self.low)) # keep every low <= every high
if len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high))
def median(self):
if len(self.low) > len(self.high):
return -self.low[0]
return (-self.low[0] + self.high[0]) / 2
Common bugs
- Using a max-heap for "k largest": you would keep everything. Keep a min-heap of size k and drop from the bottom.
- Forgetting that
heapqis a min-heap and getting the order backwards. Negate for a max-heap. - Ties in tuples:
(priority, node)crashes in Python 3 when two priorities are equal and nodes can't be compared. Add a counter or index as the second field. - Building the heap with repeated pushes when you have all items:
heapifyis O(n). - Returning
heapas if it were sorted. A heap list is only partly ordered; sort it if the order matters.
Say this in the interview
- "I keep a min-heap of the k largest so far. The root is the weakest of them, so each new value either beats it and replaces it, or is ignored. O(n log k) time, O(k) space."
- "If k is close to n, quickselect is O(n) on average, but the heap also works on a stream."
Problems for this pattern
- Last Stone Weight: a max-heap, smash the two largest.
- Kth Largest Element in an Array: the size-k heap.
- Top K Frequent Elements: count, then a heap.
- K Closest Points to Origin: a max-heap of size k by distance.
- Task Scheduler: a max-heap of remaining counts.
- Merge k Sorted Lists: k-way merge.
- Find Median from Data Stream: two heaps.
- Sliding Window Median: two heaps with lazy deletion as the window moves.
Related
Heaps · Intervals (rooms as a heap of end times) · Graph BFS and DFS (Dijkstra) · Greedy