## Algorithm

Problem Name: 295. Find Median from Data Stream

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

• For example, for `arr = [2,3,4]`, the median is `3`.
• For example, for `arr = [2,3]`, the median is `(2 + 3) / 2 = 2.5`.

Implement the MedianFinder class:

• `MedianFinder()` initializes the `MedianFinder` object.
• `void addNum(int num)` adds the integer `num` from the data stream to the data structure.
• `double findMedian()` returns the median of all elements so far. Answers within `10-5` of the actual answer will be accepted.

Example 1:

```Input
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.findMedian(); // return 2.0
```

Constraints:

• `-105 <= num <= 105`
• There will be at least one element in the data structure before calling `findMedian`.
• At most `5 * 104` calls will be made to `addNum` and `findMedian`..

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#define PRINT(MF, D) do { } while (0)
#define DUMP(MF) do { } while (0)
​
typedef struct {
int *p;
int sz;
int n;
} MedianFinder;
​
/** initialize your data structure here. */
MedianFinder* medianFinderCreate() {
MedianFinder *mf;
int *buff;
int sz;

sz = 100;
buff = malloc(sz * sizeof(int));
mf = calloc(1, sizeof(*mf));
//assert(buff && mf);
mf->p = buff;
mf->sz = sz;
​
return mf;
}
​
int find_x(int *p, int start, int end, int num) {
int x = 0;
while (start  < = end) {
x = (end + start) / 2;
if (p[x] > num) {
end = x - 1;
} else if (p[x]  <  num) {
start = x + 1;
} else {
break;
}
}
return x;
}
void medianFinderAddNum(MedianFinder* mf, int num) {
int i, x;

if (!mf) return;

if (mf->n == mf->sz) {
// enlarge the buffer
mf->sz *= 2;
mf->p = realloc(mf->p, mf->sz * sizeof(int));
//assert(mf->p);
}
if (mf->n == 0) {
mf->p[mf->n ++] = num;
DUMP(mf);
return;
}

x = find_x(mf->p, 0, mf->n - 1, num);
if (mf->p[x]  < = num) x ++;
for (i = mf->n - 1; i >= x; i --) {
mf->p[i + 1] = mf->p[i];
}
mf->p[x] = num;
mf->n ++;
DUMP(mf);
}
​
double medianFinderFindMedian(MedianFinder* mf) {
double d;

if (mf->n % 2) {
d = mf->p[mf->n / 2];
} else {
d  = mf->p[mf->n / 2];
d += mf->p[mf->n / 2 - 1];
d /= 2;
}
PRINT(mf, d);
return d;
}
​
void medianFinderFree(MedianFinder* mf) {
free(mf->p);
free(mf);
}
``````
Copy The Code &

Input

cmd

Output

cmd
[null, null, null, 1.5, null, 2.0]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {}

(left.empty() || num <= left.top()) ? left.push(num) : right.push(num);
if(left.size() > right.size() + 1){
right.push(left.top());
left.pop();
}
if(right.size() > left.size()){
left.push(right.top());
right.pop();
}
}

double findMedian() {
return left.size() > right.size()? left.top() : (left.top() + right.top()) / 2.0;
}

private:
priority_queue < int>left;
priority_queue<int, vector<int>, greater < int>>right;
};
``````
Copy The Code &

Input

cmd

Output

cmd
[null, null, null, 1.5, null, 2.0]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class MedianFinder {

private final PriorityQueue minQueue;
private final PriorityQueue < Integer> maxQueue;

public MedianFinder() {
this.minQueue = new PriorityQueue<>();
this.maxQueue = new PriorityQueue < >((a, b) -> b - a);
}

if (maxQueue.size()  <  minQueue.size()) {
}
}

public double findMedian() {
return maxQueue.size() > minQueue.size() ?
((double) maxQueue.peek()) :
((maxQueue.peek() + minQueue.peek()) / (2.0));
}
}
``````
Copy The Code &

Input

cmd

Output

cmd
[null, null, null, 1.5, null, 2.0]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const MedianFinder = function() {
this.arr = [];
};

const bs = n => {
let start = 0;
let end = this.arr.length;
while (start  <  end) {
let mid = ~~((start + end) / 2);
if (n > this.arr[mid]) start = mid + 1;
else end = mid;
}
this.arr.splice(start, 0, n);
};
if (this.arr.length === 0) this.arr.push(num);
else bs(num);
};

MedianFinder.prototype.findMedian = function() {
const mid = ~~(this.arr.length / 2);
return this.arr.length % 2 === 0
? (this.arr[mid - 1] + this.arr[mid]) / 2
: this.arr[mid];
};
``````
Copy The Code &

Input

cmd

Output

cmd
[null, null, null, 1.5, null, 2.0]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class MedianFinder:

def __init__(self):
self.l = []
self.r = []
self.m = []

if not self.m:
self.m = [num]
elif len(self.m) == 1:
m = self.m[0]
if num >= m:
self.m = [m, heapq.heappushpop(self.r, num)]
else:
self.m = [-heapq.heappushpop(self.l, -num), m]
else:
m1, m2 = self.m
if num >= m2:
heapq.heappush(self.r, num)
heapq.heappush(self.l, -m1)
self.m = [m2]
elif num <= m1:
heapq.heappush(self.l, -num)
heapq.heappush(self.r, m2)
self.m = [m1]
else:
heapq.heappush(self.l, -m1)
heapq.heappush(self.r, m2)
self.m = [num]

def findMedian(self):
return sum(self.m) / len(self.m)
``````
Copy The Code &

Input

cmd

Output

cmd
[null, null, null, 1.5, null, 2.0]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0295_FindMedianFromDataStream
{

/** initialize your data structure here. */
public _0295_FindMedianFromDataStream()
{
minPQ = new MinPriorityQueue();
maxPQ = new MaxPriorityQueue();
}

{
minPQ.Insert(num);
maxPQ.Insert(minPQ.DeleteMin());

if (minPQ.Size()  <  maxPQ.Size())
minPQ.Insert(maxPQ.DeleteMax());
}

public double FindMedian()
{
if (minPQ.Size() > maxPQ.Size())
return minPQ.Min();
else
return (minPQ.Min() + maxPQ.Max()) / 2.0;
}

public class MinPriorityQueue : PriorityQueue
{
public MinPriorityQueue() : base() { }

public MinPriorityQueue(int initCapacity) : base(initCapacity) { }

protected override void Sink(int k)
{
while (2 * k  < = N)
{
int j = 2 * k;
if (j < N && pq[j] > pq[j + 1]) j++;
if (pq[k]  < = pq[j]) break;
Swap(k, j);
k = j;
}
}

protected override void Swim(int k)
{
while (k > 1 && pq[k / 2] > pq[k])
{
Swap(k / 2, k);
k = k / 2;
}
}

public int Min() => First();

public int DeleteMin() => Delete();
}

public class MaxPriorityQueue : PriorityQueue
{
public MaxPriorityQueue() : base() { }

public MaxPriorityQueue(int initCapacity) : base(initCapacity) { }

protected override void Sink(int k)
{
while (2 * k  < = N)
{
int j = 2 * k;
if (j < N && pq[j] < pq[j + 1]) j++;
if (pq[k] >= pq[j]) break;
Swap(k, j);
k = j;
}
}

protected override void Swim(int k)
{
while (k > 1 && pq[k / 2]  <  pq[k])
{
Swap(k / 2, k);
k = k / 2;
}
}

public int Max() => First();

public int DeleteMax() => Delete();
}

public abstract class PriorityQueue
{
protected int N;
protected int[] pq;

public PriorityQueue() : this(1) { }

public PriorityQueue(int initCapacity)
{
this.N = 0;
pq = new int[initCapacity + 1];
}

public bool IsEmpty() => N == 0;

public int Size() => N;

public int First()
{
if (IsEmpty()) { throw new ArgumentOutOfRangeException(); }
return pq[1];
}

public void Insert(int x)
{
if (N >= pq.Length - 1)
Resize(pq.Length * 2);

pq[++N] = x;
Swim(N);
}

protected abstract void Swim(int k);

public int Delete()
{
var result = pq[1];
Swap(1, N--);
Sink(1);
pq[N + 1] = 0;
if (N > 0 && N == (pq.Length - 1) / 4)
Resize(pq.Length / 2);

return result;
}

protected abstract void Sink(int k);

private void Resize(int newCapacity)
{
var temp = new int[newCapacity + 1];
for (int i = 1; i  < = N; i++)
temp[i] = pq[i];

pq = temp;
}

protected void Swap(int index1, int index2)
{
var temp = pq[index1];
pq[index1] = pq[index2];
pq[index2] = temp;
}
}
}
}
``````
Copy The Code &

Input

cmd