Introduction

Heaps are the standard solution for maintaining a running median in a stream, but they are not the right tool if your goal is a strict one-shot O(n) median for a fixed array. That distinction is important because the phrase "linear time using heaps" mixes two different problems.

For a stream, two heaps give excellent incremental performance: O(log n) per insertion and O(1) median lookup. For a single static array where you want true linear-time selection, quickselect is the usual answer instead.

The Two-Heap Streaming Median Pattern

The classic heap approach keeps:

• a max-heap for the lower half of the numbers
• a min-heap for the upper half of the numbers

In Python, heapq is a min-heap, so the lower heap is often simulated by pushing negative values:

1import heapq
2
3class MedianFinder:
4    def __init__(self):
5        self.low = []   # max-heap via negative numbers
6        self.high = []  # min-heap
7
8    def add(self, value):
9        heapq.heappush(self.low, -value)
10        heapq.heappush(self.high, -heapq.heappop(self.low))
11
12        if len(self.high) > len(self.low):
13            heapq.heappush(self.low, -heapq.heappop(self.high))
14
15    def median(self):
16        if len(self.low) > len(self.high):
17            return -self.low[0]
18        return (-self.low[0] + self.high[0]) / 2
19
20
21mf = MedianFinder()
22for x in [5, 15, 1, 3]:
23    mf.add(x)
24    print(mf.median())

This is the right solution when numbers arrive one by one and you need the median after each insertion.

Why This Is Not Strict O(n) for a Static Input

If you already have all n numbers and insert them one at a time into heaps, each insertion costs O(log n). That makes the total time O(n log n), not O(n).

So heaps are efficient, but not linear-time in the strict asymptotic sense for the one-shot median problem.

That is the core correction behind this question: heaps are excellent for dynamic medians, not for proving linear-time selection on a fixed batch of numbers.

If You Need True Linear-Time Selection

For a static array, use a selection algorithm such as quickselect. Quickselect has expected O(n) time and finds the kth order statistic directly without maintaining heaps.

A simple quickselect implementation for the middle element looks like this:

1def quickselect(nums, k):
2    pivot = nums[len(nums) // 2]
3    lows = [x for x in nums if x < pivot]
4    highs = [x for x in nums if x > pivot]
5    pivots = [x for x in nums if x == pivot]
6
7    if k < len(lows):
8        return quickselect(lows, k)
9    if k < len(lows) + len(pivots):
10        return pivot
11    return quickselect(highs, k - len(lows) - len(pivots))
12
13
14def median(nums):
15    n = len(nums)
16    if n % 2 == 1:
17        return quickselect(nums, n // 2)
18    left = quickselect(nums, n // 2 - 1)
19    right = quickselect(nums, n // 2)
20    return (left + right) / 2
21
22
23print(median([5, 15, 1, 3]))

This is the more appropriate direction if the question is really about linear-time median selection for a fixed set.

Pick the Right Algorithm for the Real Problem

Use heaps when:

• numbers arrive incrementally
• you need the median after each insertion
• you want a stable online data structure

Use selection algorithms when:

• all numbers are already available
• you need one median, not a running median
• the time target is strict linear selection rather than online maintenance

That distinction saves a lot of confusion in interviews and algorithm discussions.

Common Pitfalls

• Calling the two-heap streaming approach "linear time" for a fixed batch of n inserted values.
• Using heaps when the real requirement is one-shot selection from a static array.
• Forgetting that Python's heapq is a min-heap and a max-heap needs negation.
• Failing to rebalance the two heaps, which breaks the median invariant.
• Confusing expected O(n) quickselect with guaranteed O(n) worst-case selection algorithms.

Summary

• Two heaps are the standard running-median solution, not a strict one-shot linear-time selection algorithm.
• For streaming data, heaps are excellent: O(log n) insert and O(1) median lookup.
• For a static array and one median query, quickselect is the more appropriate linear-time idea.
• The right answer depends on whether the problem is online or offline.
• The important fix is to separate "using heaps well" from "achieving strict linear time."