What you will learn
- Why a min-heap of size k finds the k largest items.
- Merging k sorted sequences with a heap of “next candidates”.
- The two-heap running median.
Signals
- “K largest / smallest / most frequent / closest”.
- “Merge k sorted lists or arrays”, “next smallest across many sources”.
- “Median of a stream”, scheduling by earliest deadline or end time.
Python’s heapq in one minute
heapq is a min-heap on a plain list: heappush and heappop are O(log n), heap[0] is the smallest. For a max-heap, push negated values. Tuples compare element by element, so (priority, tiebreaker, item) is the usual entry shape.
Code
"""Heaps: top-k, merge k sorted lists, running median."""
import heapq
def k_largest(nums, k):
heap = [] # min-heap of the k largest seen so far
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest of the k+1
return sorted(heap, reverse=True)
def merge_sorted(lists):
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))
return out
class RunningMedian:
def __init__(self):
self.low = [] # max-heap (negated) of the smaller half
self.high = [] # min-heap of the larger half
def add(self, x):
heapq.heappush(self.low, -x)
heapq.heappush(self.high, -heapq.heappop(self.low)) # move the largest low to 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
if __name__ == "__main__":
print(k_largest([3, 2, 1, 5, 6, 4], 2))
print(merge_sorted([[1, 4, 5], [1, 3, 4], [2, 6]]))
rm = RunningMedian()
medians = []
for x in [5, 15, 1, 3, 8]:
rm.add(x)
medians.append(rm.median())
print(medians)
Output:
[6, 5]
[1, 1, 2, 3, 4, 4, 5, 6]
[5, 10.0, 5, 4.0, 5]
- k largest: keep a min-heap of at most k items; when it grows to k+1, pop the smallest. What remains are the k largest. O(n log k) time, O(k) space; better than sorting when k ≪ n.
- Merge k sorted lists: the heap holds one “next” element per list. Pop the smallest, push its successor. O(N log k) for N total elements. The list index
ibreaks ties so Python never compares incomparable items. - Running median:
lowis a max-heap of the smaller half,higha min-heap of the larger half. Each add routes throughlowtohighand rebalances solowhas the same size or one more. The median islow’s top or the average of both tops.
Heap vs sorting vs quickselect
| Need | Best tool |
|---|---|
| Top k once, k small | Size-k heap, O(n log k) |
| Top k once, average O(n) | Quickselect (worst case O(n²)) |
| Top k as data streams in | Heap |
| Everything in order | Sort |
Practise: heap / priority queue problems. Heaps also power Dijkstra’s algorithm and meeting rooms.
Key takeaways
- Size-k min-heap → k largest; size-k max-heap → k smallest.
- Merge k sorted sources with one candidate per source in a heap.
- Two heaps keep a running median with O(log n) adds and O(1) reads.
- Add a tiebreaker to heap tuples when items themselves aren’t comparable.
Exercises
- K closest points to the origin using a size-k max-heap.
- Reorganise a string so no two adjacent characters are equal (max-heap by count).
- Find the k-th largest element with quickselect and compare timings with the heap on 10⁶ numbers.
Quiz
- Why use a min-heap to find the k largest elements?
- What’s the complexity of merging k lists with N total elements?
- In the running median, what size invariant do the heaps keep?
Show answers
- Its top is the smallest of the current top-k, which is exactly the one to evict when a bigger element arrives.
- O(N log k): each element is pushed and popped once on a heap of at most k entries.
lowhas either the same number of elements ashighor exactly one more.