These are my data structures and algorithms notes, cleaned up into nineteen posts, one pattern at a time. This one covers heaps and priority queues: how a heap lives in a plain list, push and pop, building a heap in linear time, and the two-heaps pattern for running middle values.
A sorted array answers every ordering question, but it charges O(n) to insert. A heap answers exactly one question, “what is the smallest (or largest) item right now?”, and in exchange it inserts and removes in O(log n). Most heap problems are the same move in disguise: stop maintaining an order you never read, keep only the part you do.
In the order this series follows, this topic comes after Trees, because a heap is a binary tree with one rule stored inside an array. It unlocks Intervals, Greedy and Advanced Graphs, where “always take the cheapest next thing” is almost always a heap underneath (Dijkstra and Prim’s are both built on one).
The prerequisites here are Heap Properties, Push and Pop, Heapify and Two Heaps. Each is one module below, in that order. How to use this post: Part 1, the method. Checkpoints have no answers on the page: work them out, then open the linked chat to have your answer checked.
Heap Properties
Foundation
Think of a company org chart where the only rule is “every manager is senior to their direct reports.” You can’t tell whether someone in marketing is senior to someone in finance, but you know for certain the CEO is the most senior person in the building. That’s a heap: a partial order that pins down the top and nothing else.
A min-heap is a binary tree with two properties:
- Order property: every node is less than or equal to its children. So the root is the minimum. (A max-heap flips it: every node is greater than or equal to its children.)
- Shape property: the tree is complete. Every level is full except possibly the last, and the last level fills left to right with no gaps.
The problem it solves: repeatedly getting the minimum of a collection that keeps changing, without paying to keep the whole thing sorted.
Mechanics
The shape property is what lets a heap live in a plain list with no node objects and no pointers. Number the nodes level by level, left to right, starting at 0. Then for the node at index i (0-indexed, which is what Python’s heapq uses):
- left child: 2i + 1
- right child: 2i + 2
- parent: (i - 1) // 2
Why is this safe? Because a complete tree has no holes, level d holds indices 2^d - 1 through 2^(d+1) - 2, and the children of consecutive nodes are consecutive indices. Take the worked example:
h = [2, 5, 3, 9, 6, 4, 8]
Index 1 (value 5) has children at 2·1+1 = 3 and 2·1+2 = 4, values 9 and 6. Index 5 (value 4) has parent (5-1)//2 = 2, value 3. Every parent is at most its children: 2 ≤ 5, 2 ≤ 3, 5 ≤ 9, 5 ≤ 6, 3 ≤ 4, 3 ≤ 8. It’s a valid min-heap.
Three consequences you’ll lean on constantly:
- The minimum is h[0]. Follow parents from any node and the values never increase, and every path ends at the root.
- Height is floor(log2 n). A complete tree with n nodes has floor(log2 n) + 1 levels. For n = 7 that’s height 2, for n = 8 it’s height 3. Every operation in the next module walks one root-to-leaf path, so this is where O(log n) comes from.
- Leaves are indices n // 2 through n - 1. Index i has a left child only if 2i + 1 ≤ n - 1, i.e. i ≤ (n - 2) / 2. For n = 7, indices 0, 1, 2 are internal and 3, 4, 5, 6 are leaves. About half the heap is leaves.
What the heap does not tell you: anything about siblings or cousins. In h, 5 sits above 3’s children 4 and 8 in the drawing, yet 5 > 4. The array is not sorted and a heap is not searchable. Finding an arbitrary value is O(n).
Some courses and textbooks (recalled, not derived here) store the heap 1-indexed with a dummy at index 0, which makes the formulas 2i, 2i + 1 and i // 2. Same structure, shifted by one. In Python you’ll use heapq, which is 0-indexed, so the 0-indexed formulas are the ones worth memorising.
Diagram
Implementation
def parent(i):
return (i - 1) // 2 # parent(5) = 2, parent(6) = 2; never called for i = 0
def left(i):
return 2 * i + 1 # left(1) = 3
def right(i):
return 2 * i + 2 # right(1) = 4
def is_min_heap(h):
# Checking each child against its own parent covers every parent-child edge
# exactly once: child indices are 1..len(h)-1, each has exactly one parent.
for i in range(1, len(h)):
if h[parent(i)] > h[i]:
return False
return True
h = [2, 5, 3, 9, 6, 4, 8]
print(is_min_heap(h)) # True
print(is_min_heap([2, 5, 3, 9, 6, 1, 8])) # False: h[5] = 1 < its parent h[2] = 3
print(is_min_heap([]), is_min_heap([7])) # True True (no edges to violate)
print(len(h) // 2) # 3, the first leaf index for n = 7
Complexity: each index formula is O(1). is_min_heap is O(n) time, O(1) extra space, where n = len(h).
Recognition
The heap properties themselves are rarely the thing a problem asks about. What you’re recognising is whether the problem only ever needs the extreme element:
- “Repeatedly take the smallest / largest / cheapest / closest / earliest.”
- A collection that changes between those queries (items added, the top removed).
- You never need the second-largest by rank directly, never need to search for a value, never need sorted iteration.
When NOT to use a heap: if you need to find or delete an arbitrary value, a hash set or a balanced BST (from Trees) fits better. If the data is static and you read it in order once, just sort it. A heap is also not a BST: a BST orders left < node < right, which supports search; a heap orders only parent vs. child, which supports only “get the top.”
Pitfalls
- Mixing 0-indexed and 1-indexed formulas. With 0-indexing, parent is (i - 1) // 2, not i // 2. i // 2 gives parent(2) = 1, which is wrong (index 2 is a child of 0).
- Assuming the array is sorted. h[1] is not the second smallest in general; it’s one of two candidates (h[1] or h[2]). A printed heap won’t look sorted, and that’s correct.
Active Recall
Answer out loud or on paper first.
-
In h = [2, 5, 3, 9, 6, 4, 8], where can the second smallest value live, and where can the third smallest live?
-
Change h[4] from 6 to 1. Which parent-child pairs now violate the order property?
-
Is every sorted array a valid min-heap? Is every valid min-heap sorted?
Mini-task
No problem in this topic’s list asks you to derive the array layout or index arithmetic from scratch (they all use heapq), so this checkpoint is included.
You’re given a list that is a valid min-heap of n ≥ 1 numbers. Return its largest value. Doing it correctly is easy; the question is how few elements you can get away with inspecting, and why that’s safe.
Before opening the chat, write down: the observation, the approach, why it’s correct, the complexity.
Transfer test
You’re building a feature where users type a username and you must say whether it’s already taken, among ten million names that change all day. Would you store the names in a heap? Why?
Push and Pop
Foundation
Push and pop are the two edits a heap supports, and both follow the same plan: make the edit in the one place that keeps the tree complete (the end of the array), then repair the order property by walking a single path.
- Push is a new employee joining at the bottom of the org chart. If they’re more senior than their manager, they swap places, and keep climbing until their manager outranks them.
- Pop is the CEO leaving. The most junior person at the bottom is temporarily placed in the CEO’s chair, then keeps swapping with their more senior direct report until nobody below outranks them.
Mechanics
Push (sift up). Append the value at index n (keeps the shape). Only one edge can now be broken: the one between the new index and its parent. While the new value is smaller than its parent, swap them and move up.
Why is each swap safe? Say the new value x is at index i with parent p, and h[p] > x. After swapping, x is at p. Its new children are the old h[p] (which is > x) and h[p]’s other child (which was ≥ h[p] > x). So the edges below x are fine and only the edge above x might still be broken. The loop keeps that invariant: at most one broken edge, directly above the moving value.
On the worked example h = [2, 5, 3, 9, 6, 4, 8], pushing 1 lands it at index 7 and it climbs 7 → 3 → 1 → 0, beating 9, then 5, then 2 (step by step in the diagram). Result: [1, 2, 3, 5, 6, 4, 8, 9], three swaps, which is the height of an 8-node heap (floor(log2 8) = 3).
Pop (sift down). Save h[0] to return. Move the last element to index 0 and shrink the list (keeps the shape). Now only the edges between the root and its children can be broken. While the moving value is larger than its smaller child, swap with that smaller child and move down.
Why the smaller child specifically? The child you promote becomes the parent of the other child. If you promote the smaller one, it’s ≤ its sibling, so the new edge is fine. Promote the larger one and you’ve just made a parent larger than its child. Concretely: [9, 2, 3]. Swap 9 with 2 gives [2, 9, 3], valid. Swap 9 with 3 gives [3, 2, 9], and 3 > 2 breaks the order.
Continuing the example, pop from [1, 2, 3, 5, 6, 4, 8, 9]: save 1, move the last value 9 to the root, then 9 sinks 0 → 1 → 3, swapping with the smaller child each time (2 over 3, then 5 over 6), and stops at index 3, a leaf (2·3+1 = 7 > 6). It returns 1 and the heap is back to exactly the original h. (That round trip is a coincidence of this example, not a rule.)
Both operations touch one root-to-leaf path, so each is O(log n), and peeking at h[0] is O(1).
Diagram
Implementation
Writing these once by hand is how you stop treating heapq as magic:
def push(heap, val):
heap.append(val) # index len(heap)-1 keeps the tree complete
i = len(heap) - 1
while i > 0:
p = (i - 1) // 2
if heap[p] <= heap[i]: # the only edge that can be broken is p -> i;
break # if it holds, every edge holds
heap[p], heap[i] = heap[i], heap[p]
i = p # push 1 into h: i goes 7 -> 3 -> 1 -> 0
def pop(heap):
if not heap:
raise IndexError("pop from empty heap")
top = heap[0]
last = heap.pop() # removing the last slot keeps the tree complete
if heap: # if the heap had one element, last IS top; nothing to fix
heap[0] = last
i, n = 0, len(heap)
while True:
l, r = 2 * i + 1, 2 * i + 2
smallest = i
if l < n and heap[l] < heap[smallest]:
smallest = l
if r < n and heap[r] < heap[smallest]:
smallest = r
# smallest is now the index of min(heap[i], heap[l], heap[r]) among
# those that exist. Promoting that child keeps it <= its sibling.
if smallest == i: # heap[i] <= both children: order restored
break
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest # pop from [1,2,3,5,6,4,8,9]: i goes 0 -> 1 -> 3
return top
h = [2, 5, 3, 9, 6, 4, 8]
push(h, 1)
print(h) # [1, 2, 3, 5, 6, 4, 8, 9]
print(pop(h), h) # 1 [2, 5, 3, 9, 6, 4, 8]
Both branches of the sift-down comparison were checked on the trace: at index 0 the left child won (2 < 3), and at index 1 the left child won again (5 < 6). For the right-child branch, take [8, 5, 3]: left 5 < 8 makes smallest = 1, then right 3 < 5 makes smallest = 2, and the swap gives [3, 5, 8]. I also ran these against heapq on 3,000 random push/pop sequences with duplicates; every popped value matched.
Complexity: push and pop are O(log n) time, O(1) extra space, where n is the heap size. Peek (heap[0]) is O(1).
The Python you’ll actually write. heapq works on a plain list and is a min-heap only (recalled: the standard library has no max-heap API for general use).
import heapq
h = [2, 5, 3, 9, 6, 4, 8]
heapq.heappush(h, 1)
print(h) # [1, 2, 3, 5, 6, 4, 8, 9] same layout as the hand-written push
print(heapq.heappop(h)) # 1
print(h[0]) # 2, peek without removing
# Max-heap: store negatives. The smallest negative is the largest original.
m = []
for x in [4, 1, 7]:
heapq.heappush(m, -x)
print(-m[0]) # 7
# Priority + payload: tuples compare element by element, so the first field is the key.
t = []
for item in [(2, "b"), (1, "z"), (2, "a")]:
heapq.heappush(t, item)
print([heapq.heappop(t) for _ in range(3)]) # [(1, 'z'), (2, 'a'), (2, 'b')]
# Push-then-pop in one sift (recalled: heappushpop pushes first, heapreplace pops first).
print(heapq.heappushpop([2, 5, 3, 9, 6, 4, 8], 1)) # 1: the new value was already the smallest
print(heapq.heappushpop([2, 5, 3, 9, 6, 4, 8], 7)) # 2: 7 goes in, the old minimum 2 comes out
Recognition
- “Process items in priority order, but new items keep arriving while you process.” A sort can’t handle arrivals; a heap can.
- “Repeatedly combine / take the two smallest (or largest).” That’s pop, pop, push.
- “The k largest / k smallest / k closest.” A heap that never holds more than k items: a min-heap of size k keeps the k largest seen so far, because its root is the weakest member and is the one to evict. This inversion (min-heap for largest) is the single most useful heap idea in interviews. It gives O(n log k) instead of sorting’s O(n log n).
- “Merge several sorted sources”: keep one candidate per source in a heap and pop the smallest.
In the list, the “keep k” signal shows up in Kth Largest Element In a Stream, K Closest Points to Origin and Kth Largest Element In An Array; “repeatedly take the largest two” shows up in Last Stone Weight; “merge sorted sources” and “always pick the best available” show up in Design Twitter and Task Scheduler.
When NOT to use it: if all items are known up front and you consume them all in order, sorting once is simpler and has the same O(n log n). If the priority is small integers (like counts bounded by n), bucket sort (Arrays & Hashing) can beat a heap. If items expire by position in a window, a monotonic deque (Sliding Window) is usually cleaner.
Pitfalls
- Forgetting heapq is a min-heap. Wanting the largest and pushing raw values gives you the smallest. Negate on the way in and on the way out, both times.
- Negating the wrong field. With tuples, negate the key only: (-dist, x, y), not the whole tuple.
- Tuple ties that fall through to incomparable payloads. Equal keys make Python compare the next field. I checked: pushing (5, Node()) then (5, Node()) raises TypeError: ‘<’ not supported between instances of ‘Node’ and ‘Node’. Add a tie-breaker counter: (5, 0, node), (5, 1, node). It’s data-dependent (two empty dicts compare equal and don’t crash, two different dicts do), so it slips past small tests.
- heappop on an empty list raises IndexError. Check
if heap:first. - Calling heappush on a list that isn’t a heap. heapq doesn’t check; it silently gives wrong answers.
Active Recall
Answer out loud or on paper first.
-
Push 10 into h = [2, 5, 3, 9, 6, 4, 8]. How many swaps happen, and why?
-
Pop from h = [2, 5, 3, 9, 6, 4, 8] (the original, not the one with 1 pushed). What does it return and what’s the final array?
-
In sift-down, why must the swap go to the smaller child? Give a three-element counterexample.
-
You want the 3 largest values from a stream using a heap that never holds more than 3 items. Min-heap or max-heap, and what do you do when a new value arrives and the heap is full?
Mini-task
Skipped: Design Twitter requires deriving a heap-driven merge of several sorted sources from scratch, so push/pop mechanics get exercised independently there. We’ll cover that reasoning when solving it.
Transfer test
An emergency room admits patients continuously. Each has a severity from 1 to 5 (5 is most urgent), and among equal severity the earlier arrival goes first. A doctor frees up and asks “who’s next?” several hundred times a day. Would you use a heap? Why?
Heapify
Foundation
Heapify turns an arbitrary list into a heap in place. The obvious way is to push the n items one by one, O(n log n). Heapify does it in O(n) by fixing the tree from the bottom up: a leaf is already a valid one-node heap, so start with the lowest nodes that have children and work toward the root, fixing each small subtree before you touch the subtree above it.
Mechanics
Take the worked example a = [8, 6, 7, 2, 5, 1, 3], n = 7.
- Leaves (indices n // 2 = 3 through 6) are already heaps. Skip them.
- For i from n // 2 - 1 down to 0, sift a[i] down (the same loop as pop’s repair).
Why is sift-down on index i safe? Sift-down assumes both of i’s subtrees are already valid heaps, and only i itself may be out of place. Going right to left, bottom to top guarantees that: i’s children have larger indices, so their subtrees were fixed earlier.
The run (each step is in the diagram): i = 2 sinks 7 below 1, i = 1 sinks 6 below 2, and i = 0 sinks 8 two levels, first below 1 and then below 3. Result: [1, 2, 3, 6, 5, 7, 8], 4 swaps total.
Why O(n) and not O(n log n). A node at height k (k levels above the bottom) can sift at most k steps. About half the nodes are leaves (height 0, zero work), a quarter have height 1, an eighth height 2, and so on. The total is n·(0/2 + 1/4 + 2/8 + 3/16 + …), and that series converges to a constant (recalled: the sum of node heights in a complete binary tree is at most n - 1). The expensive nodes near the root are few; the many nodes near the bottom are cheap. Pushing one by one gets this backwards: most of the pushes happen when the heap is already deep.
I measured it on the worst case for a min-heap (input in descending order):
| n | swaps, heapify | swaps, n pushes |
|---|---|---|
| 7 | 4 | 10 |
| 1,000 | 992 | 7,987 |
| 1,000,000 | 999,988 | 17,951,445 |
Heapify stays under n; one-by-one pushes grow like n log n.
Diagram
Implementation
def sift_down(a, i, n):
# Precondition: the subtrees rooted at 2i+1 and 2i+2 are already heaps.
while True:
l, r = 2 * i + 1, 2 * i + 2
s = i
if l < n and a[l] < a[s]:
s = l
if r < n and a[r] < a[s]:
s = r
if s == i:
return
a[i], a[s] = a[s], a[i]
i = s
def heapify(a):
n = len(a)
# Internal nodes are indices 0 .. n//2 - 1 inclusive (0..2 for n = 7).
# Visiting them from n//2 - 1 down to 0 means both children of i (indices > i)
# were already fixed, so sift_down's precondition holds every time.
for i in range(n // 2 - 1, -1, -1):
sift_down(a, i, n)
a = [8, 6, 7, 2, 5, 1, 3]
heapify(a)
print(a) # [1, 2, 3, 6, 5, 7, 8]
import heapq
b = [8, 6, 7, 2, 5, 1, 3]
heapq.heapify(b) # in place, returns None
print(b) # [1, 2, 3, 6, 5, 7, 8]
e, s = [], [5]
heapify(e); heapify(s)
print(e, s) # [] [5] (for n = 0 and n = 1 the range is empty: nothing to do)
I checked the hand-written version on 3,000 random lists with duplicates: every result is a valid heap and a permutation of the input.
Complexity: O(n) time, O(1) extra space, where n = len(a). Getting the k smallest after that costs O(k log n) more pops. (For a one-liner, heapq.nsmallest(k, a) and heapq.nlargest(k, a) exist; recalled: they use a bounded heap internally and are best when k is small relative to n.)
Recognition
- All the data arrives at once, and then you pop repeatedly or pop and push in a loop. heapify first, then operate.
- You’re about to write a loop of n heappush calls on a list you already have. That’s the O(n log n) way to do an O(n) job.
- “Sort in place with O(1) extra space and O(n log n) worst case” is heapify plus repeated extraction (see the mini-task).
When NOT to use it: if items arrive over time, there’s nothing to heapify; push as they come. If you’re going to pop every single element anyway, heapify plus n pops is O(n log n), the same as sorting, and sorted() is simpler and faster in practice.
Pitfalls
- Starting at index 0 and going forward. Sift-down at the root first assumes subtrees that haven’t been fixed yet. Try it on [8, 6, 7, 2, 5, 1, 3] with i going 0, 1, 2: the root settles on 6 before the 2 and 1 below have risen, and you end with [6, 2, 1, 8, 5, 7, 3], where 6 > 2 at the top. Not a heap.
- Using sift-up in the loop instead of sift-down. That’s back to one-by-one inserts.
- Expecting an exact layout from heapq.heapify. On this example it matches the hand-written version, but CPython’s heapq uses a different sift strategy internally (recalled), and on 759 of 3,000 random lists I tried, the two produced different (both valid) arrays. Test heap properties or popped order, never the raw array.
h = heapq.heapify(h). It returns None, so you just replaced your list with None.- Heapifying a list you still need in original order. It’s in place; copy first.
Active Recall
Answer out loud or on paper first.
-
For n = 7, why does the loop start at index 2 and not at 6?
-
Before sift_down(a, 0, 7) runs in the trace, what must be true of indices 1 and 2, and what was the array at that moment?
-
heapify is O(n) but n pops afterward is O(n log n). So what does O(n) heapify actually buy you?
-
You heapify with your own code and with heapq.heapify and the arrays differ. Is one of them wrong?
Mini-task
No problem in this topic’s list requires deriving bottom-up heap construction from scratch (the list problems that start from a full array can call heapq.heapify as a named step), so this checkpoint is included.
Sort a list of numbers in ascending order, in place. Your constraints: O(n log n) time even in the worst case, and O(1) extra space. You may not call sorted(), list.sort(), or any library that sorts for you, and merge sort’s O(n) buffer is off the table.
Before opening the chat, write down: the observation, the approach, why it’s correct, the complexity.
Transfer test
A job runs once a night over 50 million sensor readings loaded into memory, and needs the 100 lowest readings. Would you use heapify? Why?
Two Heaps
Foundation
One heap gives you one end of the data cheaply. Some problems need a value from the middle: a percentile, a cutoff, a boundary between “in” and “out” that shifts as data arrives. Two Heaps splits the data at that boundary:
- low: a max-heap of everything below the boundary. Its root is the largest of the small side.
- high: a min-heap of everything above it. Its root is the smallest of the big side.
The two roots face each other across the boundary, so whatever you need about the boundary is at most two peeks away. Picture two queues of people sorted by height, facing each other across a line on the floor: you only ever need to look at the two people standing right at the line.
Mechanics
Worked example: a leaderboard that shows the score cutoff for the top quarter of players, updated as scores arrive. The top quarter is the best ceil(n/4) scores, where n is how many have arrived; the cutoff is the lowest score still in it. Stream: 40, 10, 90, 70, 20, 60, 80, 30.
Invariants after every add:
- Order: every value in low ≤ every value in high. Equivalently, max(low) ≤ min(high), because comparing the two roots covers all pairs.
- Size: len(high) = (n + 3) // 4, which is ceil(n/4). Then high is exactly the top quarter and high[0] is the cutoff.
Why doesn’t one min-heap capped at the top quarter work? It would, until the quarter grows. At n = 5 the target jumps from 1 to 2, and the new member must be the best score outside the top quarter so far. A capped heap threw those away. low is where they’re kept, organised so that the best of them is on top.
add(x) has two steps:
- Route: if high is non-empty and x > high[0], x belongs above the boundary, push it to high. Otherwise push it to low. Either way, order holds: in the first branch x > min(high) ≥ max(low), so x is fine in high; in the second branch, x ≤ high[0] (or high is empty), so every value in high is still ≥ x.
- Rebalance: while high is too big, pop its minimum and push it to low. While high is too small, pop low’s maximum and push it to high. Moving the boundary element across keeps order, because high’s minimum is ≥ everything in low, and low’s maximum is ≤ everything in high.
Routing changes len(high) by 0 or 1 and target by 0 or 1, so at most one move happens per add. Every step is O(log n).
Diagram
The state after each add (heaps shown sorted for readability; the real arrays are heap-ordered):
Rows 1, 3 and 5 exercise all three rebalance outcomes: too small (fill from low), too big (spill to low), and a target increase pulling the best of the rest (70) across the line.
Implementation
import heapq
class TopQuarterCutoff:
def __init__(self):
self.low = [] # max-heap via negation: every score outside the top quarter
self.high = [] # min-heap: the top quarter; self.high[0] is the cutoff
self.n = 0
def add(self, score):
self.n += 1
# Route. Branch 1: score > self.high[0] >= max(low), so score belongs above.
# Branch 2: score <= self.high[0] (or high is empty), so it can't break
# "every value in high >= every value in low".
if self.high and score > self.high[0]:
heapq.heappush(self.high, score)
else:
heapq.heappush(self.low, -score) # negate: heapq is a min-heap (recalled)
target = (self.n + 3) // 4 # ceil(n/4): n = 1..4 -> 1, n = 5..8 -> 2
# Each loop runs at most once per add (see Mechanics); both keep the order
# invariant because they move the element sitting right at the boundary.
while len(self.high) > target: # e.g. adding 90 at n = 3: 40 spills to low
heapq.heappush(self.low, -heapq.heappop(self.high))
while len(self.high) < target: # e.g. adding 20 at n = 5: 70 moves up
heapq.heappush(self.high, -heapq.heappop(self.low))
def cutoff(self):
return self.high[0] # the smallest score in the top quarter
board = TopQuarterCutoff()
for s in [40, 10, 90, 70, 20, 60, 80, 30]:
board.add(s)
print(s, board.cutoff())
# 40 40 / 10 40 / 90 90 / 70 90 / 20 70 / 60 70 / 80 80 / 30 80
I checked cutoff() after every add against a brute force (sort everything, take the ceil(n/4)-th largest) on 2,000 random streams with many duplicates, and checked max(low) ≤ min(high) each time. An all-equal stream (five 5s) also works: ties route to low and the rebalance pulls them up as needed.
Complexity: add is O(log n) time (a constant number of heap pushes and pops), cutoff is O(1), and the structure is O(n) space, where n is the number of scores added.
To use this for a different boundary, change only the target formula. Find Median From Data Stream in this topic’s list is built on this same pair of heaps; working out its size rule and what to return is part of solving it, so I’ll leave that to you.
Recognition
- A running statistic from the middle of the data: median, a percentile, “the k-th item where k grows with n,” a cutoff between two groups.
- Two sets of items with a boundary between them that moves, where items cross the boundary one at a time.
- A second variant: two heaps keyed differently, where items graduate from one to the other when some condition becomes true (a threshold is reached, a time passes). The mini-task below is this variant.
When NOT to use it: if the data is static, sort once and index. If you need to delete arbitrary items too (a sliding window over the stream), plain heaps can’t remove from the middle; you need lazy deletion (mark and skip on pop) or a sorted container. If k is fixed rather than growing with n, a single bounded heap is enough.
Pitfalls
- Forgetting one of the two negations for low. Push -x, and read -low[0] or -heappop(low). Miss one and low becomes a min-heap, and the boundary silently breaks.
- Rebalancing by size without routing first (always pushing to low, say). The size rule alone doesn’t keep order; routing plus moving the boundary element does.
- Peeking an empty heap. high[0] on an empty list is IndexError. Here high is non-empty after the first add because target ≥ 1 for n ≥ 1; your size rule might allow an empty side, so check.
- Recomputing the answer by sorting each time. That’s O(n log n) per query and throws away the point of the structure.
Active Recall
Answer out loud or on paper first.
-
After the eight scores in the worked example, add 100 and then 50. What happens at each add, and what’s the cutoff?
-
Why is low a max-heap and high a min-heap, not the other way round?
-
Suppose you skip routing and always push new scores to low, then rebalance by size. Using the example, where does it go wrong?
-
Can an add ever trigger both while loops, or the same loop twice?
Mini-task
Find Median From Data Stream is a labelled instance of this pattern rather than something you derive from nothing, so no list problem exercises the two-heaps idea independently. This checkpoint is included.
You start a studio with budget B. There are n possible projects; project i needs your budget to be at least cost[i] to start it, and on completion adds gain[i] ≥ 0 to your budget (the cost is a threshold, it isn’t spent). You can complete at most k projects, one at a time. Return the largest budget you can end with.
Example: B = 0, k = 3, projects (cost, gain) = (0, 1), (1, 2), (1, 3), (4, 6), (9, 10). The answer is 10.
Before opening the chat, write down: the observation, the approach, why it’s correct, the complexity.
Transfer test
A monitoring dashboard must show the running 90th-percentile latency of all requests since midnight, updated after every request. A teammate proposes a second requirement: “the 90th percentile over only the last 5 minutes.” Would you use two heaps for each? Why?
Integration
How the four connect. Heap Properties give the invariant (parent ≤ children, complete shape) and the index arithmetic that make the other three possible. Push and Pop are the only two edits, each a single path repair, which is where O(log n) comes from. Heapify is a bulk push that uses sift-down bottom-up to get O(n) when the data is all present up front. Two Heaps is a composition: split the data at a boundary and let two roots face each other so the middle becomes as cheap as the ends.
Almost every problem in this topic reduces to one of three shapes:
- Repeated extraction: pop the best, maybe push something back, repeat (simulation, scheduling, merging sorted sources).
- Bounded selection: keep only k items in a heap whose root is the one you’d evict (top-k, k closest, k-th largest).
- Split at a boundary: two heaps around a moving middle, or two heaps where items graduate from one to the other.
Distinguishing competing approaches.
| If the problem… | Reach for | Instead of a heap because |
|---|---|---|
| Gives all data up front and you need all of it in order | sort | same O(n log n), simpler |
| Needs one k-th element of a static array, once | quickselect (average O(n)) or heap (O(n log k)) | both are fine; know the trade: quickselect is faster on average, the heap is predictable and works on streams |
| Has priorities that are small bounded integers (counts ≤ n) | buckets | O(n), no log |
| Needs the max/min over a window that slides by position | monotonic deque (Sliding Window) | O(n) total, and expiry is by position, which a heap can’t do without lazy deletion |
| Needs search, arbitrary delete, or ordered iteration | balanced BST / sorted container | a heap only knows its root |
| Needs the extreme repeatedly while items keep arriving | heap | this is its home |
Recognition checklist for an unfamiliar problem.
- Do I repeatedly need the smallest / largest / earliest / cheapest item, and does the collection change between those requests? If both, heap.
- Do I only need k items out of many? Bounded heap of size k, with the root being the one to evict (min-heap for largest-k, max-heap for smallest-k). Cost O(n log k).
- Is the answer a middle value (median, percentile, cutoff) that must stay current? Two heaps facing each other.
- Do items become eligible over time (budget rises, clock advances) and then compete by a different key? Two heaps with different keys, one feeding the other.
- What exactly is the key? Write the tuple before coding: (key, tie-breaker, payload). Negate the key if you need a max.
- Is all the data present up front? heapify instead of n pushes.
- Do I need to delete from the middle, or search? Then a heap alone isn’t enough.
The problems
Work through these with the solving cycle from Part 1: a 15-minute honest struggle, then the key sentence, then spaced repetition. My cycle note groups heaps with trees (reconstruct the state on a small example, explain how information flows toward the root). For heaps, the struggle questions are: what goes in the heap, and what’s its key? What does the root answer, and is it the item I want or the item I’d evict? Should the heap be bounded at k? Then simulate the heap’s contents by hand on a small input before coding.
7 problems · 2 easy · 4 medium · 1 hard · tracker spreadsheet (.xlsx)
| # | Problem | Difficulty | Coach |
|---|---|---|---|
| 1 | Kth Largest Element In a Stream | Easy | ChatGPT · Claude |
| 2 | Last Stone Weight | Easy | ChatGPT · Claude |
| 3 | K Closest Points to Origin | Medium | ChatGPT · Claude |
| 4 | Kth Largest Element In An Array | Medium | ChatGPT · Claude |
| 5 | Task Scheduler | Medium | ChatGPT · Claude |
| 6 | Design Twitter | Medium | ChatGPT · Claude |
| 7 | Find Median From Data Stream | Hard | ChatGPT · Claude |
Take this lesson as a live session
To go through this lesson interactively, with a coach that waits for your answers, open it as a chat.