You just felt the O(n^2) cost of maintaining sorted order. Every insertion triggered a cascade of shifts — elements shunting right, one by one, to make room for the newcomer. The array fought back with every single insert.

But here is the thing: sorted order gives you far more information than you actually need. A fully sorted array lets you find any element by rank — the 1st smallest, the 7th smallest, the 42nd smallest. You can answer any rank query in O(1) by just reading arr[k].

The median is just one rank. The middle one. You are paying the full cost of total order to answer a single question. That is like alphabetizing your entire bookshelf every time you want to find the book in the middle.

What if you could answer the median question without sorting at all?

Forget sorting. Forget arrays. Think about partitioning.

Imagine you have a pile of numbered cards. You do not care about their exact order. You only care about one thing: which cards are in the bottom half and which are in the top half.

If you had 7 cards, the bottom pile would hold the 4 smallest and the top pile would hold the 3 largest. You do not need the piles to be internally sorted. You just need every card in the bottom pile to be smaller than every card in the top pile.

This is a much weaker requirement than full sorting — and weaker requirements are cheaper to maintain. You are not asking “what is the rank of every element?” You are asking “which side of the middle does this element fall on?” That is a binary question. Left or right. Small or large.

The partition idea feels right. But it raises an immediate question: once you have split the numbers into two piles, how do you actually find the median?

Think about where the median lives in this two-pile world.

If the bottom pile holds everything below the median and the top pile holds everything above it, then the median is trapped at the boundary between the piles. It is the largest element of the bottom pile — or the smallest element of the top pile — or the average of both, if the total count is even.

This is the key insight: you do not need to know the rank of every element. You only need access to the two elements that straddle the boundary. The biggest of the small half. The smallest of the large half. Those two values — and only those two — determine the median.

Two elements out of potentially thousands. If you could peek at those two boundary elements instantly, the median would cost you nothing to compute. One peek, or two peeks and an average. Done.

The question is no longer “how do I sort the stream?” It is “how do I get constant-time access to the boundary elements?”

Here is where the partition idea hits a wall.

If the two halves are just unsorted piles — bags of numbers with no internal structure — then finding the largest element of the bottom pile requires scanning every element in it. You have to look at each number, compare it to the current maximum, and keep going until you have checked them all. That is O(n) work.

The same is true for the smallest element of the top pile. Another full scan. Another O(n).

So you traded one O(n) operation — shifting elements during insertion — for a different O(n) operation — scanning a pile to find its extreme. The partition idea is right. Splitting into two halves captures exactly the information you need. But the data structure is wrong. An unsorted pile does not give you fast access to its boundary element.

scanning...

You need a data structure where the extreme value — the max of one pile, the min of the other — is always right there, at the top, ready to read without scanning.

What kind of structure keeps its extreme element at the surface?

Route four numbers into two piles. Every number either belongs in the small half or the large half — your job is to decide.

Your two piles are ready. Now try to find the median.

Scanning was O(n). You need O(1) access to the boundary. Think about what each pile needs to surface instantly.

You identified the operations. Now watch the structure that delivers them materialise from your buckets.

Two more numbers arrive. Route them into the heaps and watch them sift into place.

Every action you performed maps to a line of code. Explore the implementation.

What you just built has a name. The bottom pile — the one holding the smaller half — is a max-heap. A max-heap keeps its largest element at the root, always. No scanning required. One peek: O(1).

The top pile — the one holding the larger half — is a min-heap. A min-heap keeps its smallest element at the root, always. One peek: O(1).

Together, they form the two-heap structure. The max-heap's root is the largest of the small half. The min-heap's root is the smallest of the large half. Two roots. One boundary. The median is always one or two peeks away.

This is the core invariant: maxHeap.peek() <= minHeap.peek(). Every element in the max-heap is smaller than or equal to every element in the min-heap. The boundary between the two heaps is the median. Not approximately. Exactly.

You went from scanning entire piles to reading roots. From O(n) per median query to O(1). The partition insight was right all along — it just needed the right container.

Nothing is free. The O(1) median comes with an insertion cost.

When a new number arrives, you need to route it into the correct heap — compare it to the boundary and push it left or right. Inserting into a heap costs O(log n), because the heap needs to bubble the new element into its correct position to maintain the heap property. That is dramatically cheaper than the O(n) shifting you felt in the previous lesson, but it is not zero.

For n insertions, the total cost is O(n log n) — down from the O(n^2) you suffered with sorted-array insertion. And the median is accessible in O(1) at every step, without any extra work.

Here is the trade-off in plain terms: you give up full sorted order and gain constant-time access to the one rank that matters. You cannot answer “what is the 7th smallest element?” anymore. But you never needed to. The median was always the only question — and now you can answer it by reading two roots.

The sorted array wins on simplicity. The two-heap wins on the operation that actually bottlenecked you: insertion into a growing stream. And that is the operation that matters when data arrives one element at a time.