The O(n) Club: Median from Data Stream—How Heaps Became Your Streaming BFF

The O(n) Club: Median from Data Stream—How Heaps Became Your Streaming BFF

⚡ TL;DR

Still sorting your whole list every time for the median, like it’s 1999? Use two heaps: a max-heap for the little guys, a min-heap for the big ones. Insert = O(log n), median = O(1), headaches = 0. Java’s vibe below:

PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
PriorityQueue<Integer> high = new PriorityQueue<>(); // min-heap
// Insert into the right heap. Rebalance. Peek median from the tops.

🧠 How Devs Usually Mess This Up

Step 1: Dump everything into a List or array. Step 2: Sort, every single time someone asks “what’s the median?” Step 3: Realize your O(n log n) solution collapses when real data appears. Bonus fail: mixing up your heap types—watch the world burn as your max-heap becomes a min-heap, or vice versa. ☕

🔍 What’s Actually Going On

Pretend you’re running two elevators at a hackathon: one for hipster devs (max-heap, lower half), one for product managers (min-heap, upper half). Both queues stay balanced. Median = the one or two awkward people in the middle. Instead of sorting everyone every time the CEO calls for ‘the median guest,’ just peek at the top floors.

🛠️ PseudoCode

• Make two heaps:
  

  maxHeap = new PriorityQueue(Collections.reverseOrder()); // holds lower half
  minHeap = new PriorityQueue(); // holds upper half

• When adding: Toss new number into maxHeap (lower half).
• Balance them: Pop max from maxHeap, push to minHeap. If minHeap jumps ahead in size, return the favor.
• Median logic:
  • If even: Average both heap tops.
  • If odd: Top of the bigger heap gets the spotlight.

It’s like keeping two nearly equal cookie jars—just reach into the right one for perfect snacking (and medians).

💻 The Code

import java.util.*;
 class MedianFinder {
    private PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> right = new PriorityQueue<>();
    
    public void addNum(int num) {
        left.offer(num);
        right.offer(left.poll());
        if (right.size() > left.size()) {
            left.offer(right.poll());
        }
    }
     public double findMedian() {
        if (left.size() > right.size()) return left.peek();
        return (left.peek() + right.peek()) / 2.0;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Heap confusion: Java’s PriorityQueue is a min-heap. Want a max-heap? Specify Collections.reverseOrder(). No, there’s no built-in MaxHeap for you. Sorry, not sorry!
• No balance, no median: Failing to keep heaps within one of each other will make your interviewers think you failed kindergarten sharing.
• Even vs Odd: On even length, just average the two tops. Don’t go on a soul-searching journey for the answer.
• Speed check: Each add is O(log n); finding median is O(1). Stick that in your LinkedList and smoke it.

🧠 Interviewer Brain-Tattoo

“Don’t sort the ocean every time you want the tide — split it into two balanced harbors and check the captains at the top.”