LeetCode 295: Find Median from Data Stream

Explanation:

To find the median from a data stream efficiently, we can use two priority queues - one max heap to store the lower half of the elements and one min heap to store the higher half of the elements. By maintaining these two heaps, we can obtain the median in constant time.

Here's how the algorithm works:

1. Initialize two priority queues: maxHeap to store the smaller half of elements and minHeap to store the larger half of elements.
2. When adding a new number:
   • Add the number to maxHeap.
   • If the size of maxHeap is greater than the size of minHeap or the top element of maxHeap is greater than the new number, pop the top element from maxHeap and push it to minHeap.
   • If the size of minHeap is greater than the size of maxHeap, pop the top element from minHeap and push it to maxHeap.
3. To find the median:
   • If the size of maxHeap and minHeap is the same, return the average of their top elements.
   • Otherwise, return the top element of the heap with more elements.

import java.util.PriorityQueue;

class MedianFinder {
    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());

        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
}