# 7. Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.For example,

`[2,3,4]`, the median is `3`

`[2,3]`, the median is `(2 + 3) / 2 = 2.5`

Design a data structure that supports the following two operations:

* void addNum(int num) - Add a integer number from the data stream to the data structure.
* double findMedian() - Return the median of all elements so far.

**Example:**

```
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2
```

## Solution: (Bruteforce)

**Inserting into a vector.**\
**Sorting the array and finding the median**\
**Time Complexity: (n log n) for 1 query**

## Solution: (Insertion Sort)

**Median can be accessed  in O(1) time**\
**Inserting the num always in the sorted position (Finding the position and inserting) O(n)**

```cpp
class MedianFinder
{
public:
      vector<int> v;
    
    int findPos(vector<int> v,int num){
        for(int i=0;i<v.size();i++){
            if(num<v[i]){
                return i;
            }
        }
        return -1;
    }
    /** initialize your data structure here. */
  
    
    MedianFinder()
    {
    }

    void addNum(int num)
    {
        int x = findPos(v,num);
        if(v.size() == 0 || x == -1){
            v.push_back(num);
        }
        else{
            
            v.insert(v.begin()+x,num);
            
        }
        
        
    }

    double findMedian()
    {

        double med;
        if (v.size() % 2 == 0)
        {
            int mid = v.size() / 2;
            med = ((double)v[mid] + (double)v[mid - 1]) / 2;
        }
        else
        {
            int mid = v.size() / 2;
            med = v[mid];
        }

        return med;
    }
};
```

**Time Complexity: O(n)**

## Solution: (Using Heap)

**We can maintain two heap :**

**Two priority queues:**

1. **A max-heap `lo` to store the smaller half of the numbers**
2. **A min-heap `hi` to store the larger half of the numbers**

**Insertion will take O(log n) .**\
The max-heap `lo` is allowed to store, at worst, one more element more than the min-heap `hi`. When the heaps are perfectly balanced, the median can be derived from the tops of both heaps. **Median can be assessed in O(1) time.**

**Adding a number `num`:**

* **Add `num` to max-heap `lo`. Since `lo` received a new element, we must do a balancing step for `hi`. So remove the largest element from `lo` and offer it to `hi`.**
* **The min-heap `hi` might end holding more elements than the max-heap `lo`, after the previous operation. We fix that by removing the smallest element from `hi` and offering it to `lo`.**

**Approach:**\
**\[41, 35, 62, 5, 97, 108]**

```
Adding number 41
MaxHeap lo: [41]           // MaxHeap stores the largest value at the top (index 0)
MinHeap hi: []             // MinHeap stores the smallest value at the top (index 0)
Median is 41
=======================

Adding number 35
MaxHeap lo: [35]
MinHeap hi: [41]
Median is 38
=======================

Adding number 62
MaxHeap lo: [41, 35]
MinHeap hi: [62]
Median is 41
=======================

Adding number 4
MaxHeap lo: [35, 4]
MinHeap hi: [41, 62]
Median is 38
=======================

Adding number 97
MaxHeap lo: [41, 35, 4]
MinHeap hi: [62, 97]
Median is 41
=======================

Adding number 108
MaxHeap lo: [41, 35, 4]
MinHeap hi: [62, 97, 108]
Median is 51.5
```

```cpp
class MedianFinder
{
public:

    /** initialize your data structure here. */
    priority_queue<int> maxh;
    priority_queue<int, vector<int>, greater<int>> minh;
    
    MedianFinder()
    {
    }

    void addNum(int num)
    {

        maxh.push(num);

        minh.push(maxh.top());
        maxh.pop();

        if (minh.size() > maxh.size())
        {
            maxh.push(minh.top());
            minh.pop();
        }
    }

    double findMedian()
    {

        if (maxh.size() > minh.size())
        {
            return maxh.top();
        }

        return ((double)(maxh.top()) + (double)(minh.top())) * 0.5;
    }
};
```

**Time Complexity: O(log n)**


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soumyajit4419.gitbook.io/ds-algo/heap/7.-find-median-from-data-stream.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.