Two HeapsTwo heaps

01Why it exists

Reach for it when you see:Median, data stream, one half against the other half, two dimensions each with their own ordering, needing the largest and the smallest at once.

02The core idea

A single heap can tell you which element is the largest, or which is the smallest, but never which one is in the middle. Cutting the data in two solves that: put the smaller half into a max-heap, whose top is the largest value on the left, and the larger half into a min-heap, whose top is the smallest value on the right. Those two tops are exactly the two values sitting in the middle of the whole set.

Two invariants have to hold. First, every value on the left is no larger than every value on the right, that is max(low) ≤ min(high): compare a new element with the left heap's top to decide which side it belongs on. Second, the two sides differ in size by at most 1: after the insertion, if one side has grown too large, move its top across to the other. By convention the left side is the one allowed to hold the extra element, so with an odd count the median is the left heap's top, and with an even count it is the average of the two tops.

Each value costs at most one push plus one move, so O(log n); reading the median only looks at the tops, so O(1). Set against re-sorting at O(n log n) every time, this is the typical shape of a streaming problem: never recompute, just maintain.

Two heaps are not only for medians. The more general shape is one heap per dimension: the IPO problem uses one heap to unlock projects by their capital threshold and another to choose among them by profit, while the meeting-rooms problem uses one heap for start times and another for end times. Whenever you notice two ordering criteria that have to be handled at the same time, reach for this.

03The algorithm

1. 1Prepare low (a max-heap) and high (a min-heap). Python has no max-heap, so low stores negated values.
2. 2For a new element x: if low is empty or x ≤ max(low), push it onto low; otherwise push it onto high. This step maintains "left half ≤ right half".
3. 3Rebalance: if len(low) > len(high) + 1, move low's top over to high; if len(high) > len(low), move high's top over to low.
4. 4Read the median: when low holds more, return max(low); when both hold the same number, return (max(low) + min(high)) / 2.
5. 5When old elements have to be removed (a sliding window), record them in a hash table as pending deletions, pop them for real once they surface at the top, and subtract the pending count when comparing sizes.

04Interactive demo

Eight latency readings arrive in order. Notice how little work each one takes: decide which side it goes on, move one element across if that is needed, then read the median straight off the heap tops.

05Code

A full implementation of the streaming median, plus the IPO problem to show the other use of the pattern, where each heap owns one dimension.

import heapq


class MedianFinder:
    """Median of a data stream (LeetCode 295).
    low: max-heap holding the smaller half (simulated by storing negatives)
    high: min-heap holding the larger half
    Invariant: len(low) == len(high) or len(low) == len(high) + 1, and max(low) <= min(high)
    """

    def __init__(self):
        self.low = []    # stores -x
        self.high = []   # stores x

    def add_num(self, x):
        if not self.low or x <= -self.low[0]:
            heapq.heappush(self.low, -x)
        else:
            heapq.heappush(self.high, x)
        # Rebalance: low may hold at most one more than high
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

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


# The same skeleton elsewhere: IPO (LeetCode 502)
# The heaps split the work: one ordered by the capital threshold (min-heap), one by profit (max-heap)
def maximize_capital(k, w, profits, capital):
    by_capital = sorted(zip(capital, profits))     # (capital required, profit)
    available = []                                 # max-heap: stores -profit
    i = 0
    for _ in range(k):
        while i < len(by_capital) and by_capital[i][0] <= w:
            heapq.heappush(available, -by_capital[i][1])   # affordable now, so unlock it
            i += 1
        if not available:
            break
        w += -heapq.heappop(available)             # take on the most profitable one
    return w

06Practice

• LeetCode 295Find Median from Data StreamHard
• LeetCode 502IPOHard
• LeetCode 480Sliding Window Median (lazy deletion)Hard
• LeetCode 253Meeting Rooms II (one heap for the end times)Medium
• LeetCode 1825Finding MK AverageHard