Easiest Explanation || Best Solution || Priority Queue
IntuitionThe goal is to maintain a running median as numbers are continuously added to the data stream. The idea is to divide the data into two balanced halves:
# Intuition

The goal is to maintain a running median as numbers are continuously added to the data stream. The idea is to divide the data into two balanced halves:
- A max-heap (`leftHeap`) to store the smaller half of the numbers.
- A min-heap (`rightHeap`) to store the larger half of the numbers.

By maintaining these two heaps, the median can be efficiently retrieved:
- If the heaps are of equal size, the median is the average of the two middle numbers.
- If one heap has more elements, the median is the top of that heap.

# Approach

1. **Heap Setup**:
   - Use two heaps: a max-heap (`leftHeap`) for the smaller half of the numbers and a min-heap (`rightHeap`) for the larger half.
   - Use the `Comparator.reverseOrder()` to create a max-heap.

2. **Adding a Number**:
   - Depending on the size of the heaps:
     - If `leftHeap` has more elements, decide whether the new number should go into `leftHeap` or `rightHeap`. Adjust and rebalance the heaps if necessary.
     - If the heaps are of equal size, decide which heap the new number belongs to. Update the median accordingly.
     - If `rightHeap` has more elements, decide whether the new number should go into `rightHeap` or `leftHeap`. Adjust and rebalance the heaps if necessary.
   - After insertion, ensure the heaps are balanced and the median is updated.

3. **Finding the Median**:
   - If the heaps are of equal size, return the average of the two root values.
   - If one heap has more elements, return the root of the larger heap.

# Complexity

- **Time Complexity**:
  - Adding a number: \(O(\log n)\) (heap insertion and rebalancing).
  - Finding the median: \(O(1)\) (direct retrieval of heap roots).

- **Space Complexity**:
  - \(O(n)\) to store the numbers in the heaps, where \(n\) is the total number of elements added.

# Code
```java []
class MedianFinder {
    // Max-heap to store the smaller half of the numbers
    PriorityQueue<Integer> leftHeap;
    // Min-heap to store the larger half of the numbers
    PriorityQueue<Integer> rightHeap;
    // Variable to keep track of the current median
    double med;

    public MedianFinder() {
        // Initialize the leftHeap as a max-heap (reversed order)
        leftHeap = new PriorityQueue<>(Comparator.reverseOrder());
        // Initialize the rightHeap as a min-heap (natural order)
        rightHeap = new PriorityQueue<>();
        // Initialize median as an arbitrary value, 1.0
        med = 1.0;
    }

    public void addNum(int num) {
        // Case 1: leftHeap has more elements than rightHeap
        if (leftHeap.size() > rightHeap.size()) {
            if (num < med) {
                // If the new number is less than the current median,
                // move the largest element from leftHeap to rightHeap
                // and add the new number to leftHeap
                rightHeap.offer(leftHeap.poll());
                leftHeap.offer(num);
            } else {
                // If the new number is greater than or equal to the median,
                // add it directly to the rightHeap
                rightHeap.offer(num);
            }
            // Update the median as the average of the two middle elements
            med = (leftHeap.peek() + rightHeap.peek()) / 2.0;
        }
        // Case 2: leftHeap and rightHeap have equal size
        else if (leftHeap.size() == rightHeap.size()) {
            if (num < med) {
                // If the new number is less than the current median,
                // add it to leftHeap, and update the median to the top of leftHeap
                leftHeap.offer(num);
                med = (double) leftHeap.peek();
            } else {
                // If the new number is greater than or equal to the median,
                // add it to rightHeap, and update the median to the top of rightHeap
                rightHeap.offer(num);
                med = (double) rightHeap.peek();
            }
        }
        // Case 3: rightHeap has more elements than leftHeap
        else {
            if (num > med) {
                // If the new number is greater than the current median,
                // move the smallest element from rightHeap to leftHeap
                // and add the new number to rightHeap
                leftHeap.offer(rightHeap.poll());
                rightHeap.offer(num);
            } else {
                // If the new number is less than or equal to the median,
                // add it directly to leftHeap
                leftHeap.offer(num);
            }
            // Update the median as the average of the two middle elements
            med = (leftHeap.peek() + rightHeap.peek()) / 2.0;
        }
    }

    public double findMedian() {
        // Return the current median
        return med;
    }
}

```
['Heap (Priority Queue)', 'Java']