Two Heaps Pattern: Template, Median Problems and IPO

The two heaps pattern splits a changing collection into a lower half kept in a max-heap and an upper half kept in a min-heap, so the middle values sit on the two heap tops and you can read the median in O(1) and insert in O(log n). Use it when a problem asks for the median (or another boundary between "small" and "large" items) while numbers keep arriving, or when you must repeatedly pick the best item from a pool that keeps growing.

This guide covers the signals, the template, a trace, three worked LeetCode problems (295, 480 and 502), a complexity table, common bugs and a practice list. Every code block was run in Python with asserts against a brute-force check (sorting, or trying every order) before we published it. For single-heap problems such as top K and merging K lists, see the heap and priority queue pattern.

When to use the two heaps pattern

• Median of a stream: numbers arrive one at a time and you must report the median after each, or at any time.
• Median of a moving window: the same, but old values also leave.
• A boundary that moves: "the i-th best so far", where you repeatedly need the element at a rank that changes by one.
• Two pools with different orderings: items unlock by one key (cost, start time) and are chosen by another (profit, end time). One heap holds the locked items sorted by the unlock key; the other holds unlocked items sorted by the choice key.
• Sorting the whole input each time would be O(n log n) per query, and the prompt hints at something faster.

How the two heaps pattern works

Keep two heaps and two invariants:

1. Order: every value in low (the max-heap) is less than or equal to every value in high (the min-heap).
2. Size: low has the same number of elements as high, or exactly one more.

With both invariants true, the median is the top of low when the count is odd, and the average of both tops when it is even. Python's heapq is a min-heap (Python docs), so the max-heap stores negated values. Python 3.14 added max-heap functions such as heapq.heappush_max (as of October 2026), but negation works on every version, which makes it the safe choice in an interview.

Trace: adding 5, 15, 1, 3

Check against the sorted list [1, 3, 5, 15]: the two middle values are 3 and 5, so the median is 4.

The Python template (Find Median from Data Stream)

This is the full solution to Find Median from Data Stream (LeetCode 295). The insert always pushes into low, then moves low's largest value to high, then moves one back if high got bigger. That fixed three-step dance keeps both invariants without any if-else on where the number belongs.

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []    # max-heap of the smaller half (values stored negated)
        self.high = []   # min-heap of the larger half

    def addNum(self, num):
        heapq.heappush(self.low, -num)
        # move the largest value of the low half up, so every low <= every high
        heapq.heappush(self.high, -heapq.heappop(self.low))
        # keep low the same size as high, or exactly one bigger
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self):
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2

Complexity: addNum is O(log n) (a constant number of heap pushes and pops), findMedian is O(1), and space is O(n).

LeetCode 295 lists two follow-ups worth preparing: if every number is in the range 0 to 100, keep a count array of 101 buckets and walk it to the middle; if 99% of numbers are in that range, keep the count array plus small overflow structures for values below and above it.

Worked problem 1: Sliding Window Median (LeetCode 480)

Sliding Window Median (LeetCode 480): return the median of every window of size k as it slides across the array.

The idea: the same two heaps, but values also leave. Heaps cannot delete from the middle cheaply, so use lazy deletion: record the value in a delayed counter, adjust the logical size of the half it belongs to, and only physically pop it when it reaches the top of a heap. Keep separate size counters, because the heaps' list lengths include values that are already "deleted".

import heapq
from collections import defaultdict

def median_sliding_window(nums, k):
    low, high = [], []            # max-heap (negated) and min-heap
    delayed = defaultdict(int)    # value -> removals not yet popped (lazy deletion)
    low_size = high_size = 0      # counts of elements still in the window

    def prune(heap, sign):        # pop delayed values sitting on top of a heap
        while heap and delayed[sign * heap[0]]:
            delayed[sign * heap[0]] -= 1
            heapq.heappop(heap)

    def rebalance():
        nonlocal low_size, high_size
        if low_size > high_size + 1:
            heapq.heappush(high, -heapq.heappop(low))
            low_size -= 1
            high_size += 1
            prune(low, -1)
        elif low_size < high_size:
            heapq.heappush(low, -heapq.heappop(high))
            low_size += 1
            high_size -= 1
            prune(high, 1)

    def add(x):
        nonlocal low_size, high_size
        if not low or x <= -low[0]:
            heapq.heappush(low, -x)
            low_size += 1
        else:
            heapq.heappush(high, x)
            high_size += 1
        rebalance()

    def remove(x):
        nonlocal low_size, high_size
        delayed[x] += 1
        if x <= -low[0]:          # x lives in the low half
            low_size -= 1
            if x == -low[0]:
                prune(low, -1)
        else:
            high_size -= 1
            if x == high[0]:
                prune(high, 1)
        rebalance()

    result = []
    for i, x in enumerate(nums):
        add(x)
        if i >= k:
            remove(nums[i - k])
        if i >= k - 1:
            result.append(float(-low[0]) if k % 2 else (-low[0] + high[0]) / 2)
    return result

Complexity: O(n log n) time, since each value is pushed and popped a constant number of times, and O(n) space in the worst case because delayed values can linger below the tops. In Java or C++ the values can be as large as 2**31 - 1, so adding two tops can overflow; Python integers do not, but say it out loud if you code in another language.

Worked problem 2: IPO (LeetCode 502)

IPO (LeetCode 502): you start with capital w and can finish at most k projects. Each project needs a minimum capital to start and adds its profit to your capital. Maximize the final capital.

The idea: this is the "two pools" version of the pattern. A min-heap holds projects you cannot afford yet, ordered by required capital. A max-heap holds projects you can afford, ordered by profit. Before each pick, move every newly affordable project from the first heap to the second, then take the most profitable one. Greedy is safe because profits are never negative, so capital only grows and nothing affordable ever becomes unaffordable.

import heapq

def find_maximized_capital(k, w, profits, capital):
    locked = list(zip(capital, profits))
    heapq.heapify(locked)                   # min-heap: cheapest project to unlock on top
    affordable = []                         # max-heap (negated): most profitable on top
    for _ in range(k):
        while locked and locked[0][0] <= w:
            c, p = heapq.heappop(locked)
            heapq.heappush(affordable, -p)  # now affordable: move it to the other heap
        if not affordable:
            break                           # nothing we can start
        w -= heapq.heappop(affordable)      # take the best profit (stored negated)
    return w

Complexity: O(n log n + k log n) time and O(n) space. Sorting projects by capital instead of heapifying them works the same way and is equally accepted.

Complexity: two heaps vs the alternatives

To see how O(log n) and O(n) per operation diverge over 50,000 calls (LeetCode 295's limit), try the free Big-O complexity visualizer.

Common bugs and edge cases

• Forgetting to negate on both push and pop. The max-heap stores -x; every read of its top must flip the sign back.
• Breaking the order invariant. Pushing straight into whichever heap is smaller can put a large value in low. Always route through the other heap (push to low, move its top to high) or compare with low's top first.
• Letting sizes drift by two. Rebalance after every insert and every removal, not only at query time.
• Integer division for the median. Return (a + b) / 2, not //, when the count is even; LeetCode expects a float.
• Lazy deletion with the wrong size. In the sliding window version, decide which half a removed value belongs to by comparing it with low's current top, and track sizes separately from len(heap).
• Using two heaps for two sorted arrays. Median of Two Sorted Arrays (LeetCode 4) wants O(log(m + n)), which is binary search, not heaps.
• Test out loud: one element, two equal elements, all duplicates, negative numbers, and k = 1 in the window version.

Practice list: 7 two heaps problems

Problem numbers and difficulty labels were checked on LeetCode as of October 2026. Related patterns: top K elements, sliding window and merge intervals.

How to practice the two heaps pattern out loud

Interviewers often care less about the code than about whether you can state the invariants and the lazy-deletion idea clearly. Practice explaining both. CoPilot Interview's Mock Interview can include coding questions in your language; it reads each question aloud, scores your spoken answer out of 10 with what to fix and a model answer, and coding questions never auto-submit. With nothing to install, the browser mock at /ai-mock-interview has 113 questions across 9 tracks, including coding. For a one-page refresher, open the coding interview cheat sheet.

FAQ

What is the two heaps pattern?

It is a technique that keeps the smaller half of the data in a max-heap and the larger half in a min-heap. The two heap tops are the middle values, so you can read the median in O(1) time and add a number in O(log n) time.

Why use a max-heap and a min-heap to find the median?

The max-heap gives instant access to the largest value of the lower half and the min-heap to the smallest value of the upper half. Those two values are exactly the ones the median needs, and keeping the heaps balanced in size keeps them in the middle.

How do you make a max-heap in Python?

Push negated values into a heapq min-heap and negate again when you read or pop. Python 3.14 added max-heap functions such as heappush_max, but negation works in every Python version, so it is the safest choice in an interview.

What is the time complexity of Find Median from Data Stream with two heaps?

Adding a number takes O(log n) time because it does a constant number of heap pushes and pops. Finding the median takes O(1) time because it only reads the heap tops. Space is O(n).

How do you remove elements in the sliding window median problem?

Use lazy deletion. Record the value to remove in a counter, update the logical size of the half it belongs to, and pop it only when it reaches the top of its heap. Each value is pushed and popped a constant number of times, so the total is O(n log n).

Which LeetCode problems use the two heaps pattern?

The core ones are Find Median from Data Stream (295), Sliding Window Median (480) and IPO (502). Related practice includes Total Cost to Hire K Workers (2462), Find Right Interval (436) and Sequentially Ordinal Rank Tracker (2102).