# Median of stream of numbers in Java

Problem statement: Find median of stream of numbers numbers. Reference GeeksForGeeks

Median is defined as middle element of sorted elements (even count of numbers) / mean of two middle elements(odd count of numbers)
Consider array of numbers as stream of numbers
5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4
After reading 1st element of stream - 5 -> median - 5
After reading 2nd element of stream - 5, 15 -> median - 10
After reading 3rd element of stream - 5, 15, 1 -> median - 5

### Sample program to find median of numbers using Min and Max heap:-

We need to maintain two heaps say left heap as max heap and right heap as min heap. Refer how to implement max and min heap.
```public class MedianOfNumberStream {
public static void findMedianOfStream(int[] input) { // stream is passed as
// an array
Heap left = new MaxHeap();
Heap right = new MinHeap();
float median = 0;
int size = input.length;
for (int i = 0; i < size; i++) {
System.out.print("Current median of " + (i + 1) + " elements is: ");
median = computeCurrrentMedian(input[i], median, left, right);
System.out.print(median);
System.out.println();
}
}

private static float computeCurrrentMedian(int currentElement,
float median, Heap left, Heap right) {
int stat = Util.LeftOrRight(left.getSize(), right.getSize());
switch (stat) {
case 1: // Number of elements in left (max) heap > right (min) heap
if (currentElement < median) {
// Remove top element from left heap and
// insert into right heap
right.insert(left.remove());

// current element fits in left (max) heap
left.insert(currentElement);
} else {
// current element fits in right (min) heap
right.insert(currentElement);
}

// Both heaps are balanced
median = Util.average(left.getTop(), right.getTop());

break;

case 0: // Number of elements in left (max) heap = right (min) heap

if (currentElement < median) {
left.insert(currentElement);
median = left.getTop();
} else {
// current element fits in right (min) heap
right.insert(currentElement);
median = right.getTop();
}

break;

case -1: // Number of elements in left (max) heap < right (min) heap

if (currentElement < median) {
left.insert(currentElement);
} else {
// Remove top element from right heap and
// insert into left heap
left.insert(right.remove());
// current element fits in right (min) heap
right.insert(currentElement);
}
// Both heaps are balanced
median = Util.average(left.getTop(), right.getTop());
break;
}
return median;
}

public static void main(String[] args) {
//int A[] = { 5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4 };
int B[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
findMedianOfStream(B);
}
}

class MaxHeap extends Heap {
public MaxHeap() {
super(Integer.MAX_VALUE/1000, HeapType.MAX_HEAP.getValue());
}
}

class MinHeap extends Heap {
public MinHeap() {
super(Integer.MAX_VALUE/1000, HeapType.MIN_HEAP.getValue());
}
}

class Util {
public static int LeftOrRight(int a, int b) {
if (a == b)
return 0;

return a < b ? -1 : 1;
}

public static float average(int a, int b) {
return ((float) a + (float) b) / 2;
}
}

enum HeapType {
MAX_HEAP(0), MIN_HEAP(2);

private final int value;

HeapType(final int newValue) {
value = newValue;
}

public int getValue() {
return value;
}
}

class Heap {
int[] heap;
int size;
int minMaxFlag;

public Heap() {
}

public Heap(int max, int minMaxFlag) {
heap = new int[max];
size = 0;
this.minMaxFlag = minMaxFlag;
}

public int getSize() {
return size;
}

int getTop() {
int max = Integer.MAX_VALUE;

if (size >= 0) {
max = heap[0];
}

return max;
}

public int parentIndex(int index) {
return (index - 1) / 2;
}

public int leftChildIndex(int index) {
return (2 * index) + 1;
}

public int rightChildIndex(int index) {
return (2 * index) + 2;
}

public void swap(int index1, int index2) {
heap[index1] = heap[index1] ^ heap[index2];
heap[index2] = heap[index1] ^ heap[index2];
heap[index1] = heap[index1] ^ heap[index2];
}

public void insert(int element) {
if (size == 0) {
heap[size++] = element;
} else {
heap[size] = element;
percolateUp(size++);
}
}

// max/min heap based on flag
public void percolateUp(int index) {
int temp = heap[index];
int parent = parentIndex(index);
if (this.minMaxFlag == 0) {
while (index > 0 && heap[parent] < temp) {
heap[index] = heap[parent];
index = parent;
parent = parentIndex(index);

}
} else {
while (index > 0 && heap[parent] > temp) {
heap[index] = heap[parent];
index = parent;
parent = parentIndex(index);

}
}

heap[index] = temp;
}

public int remove() {
int temp = heap[0];
heap[0] = heap[--size];
percolateDown(0);
return temp;
}

public void percolateDown(int index) {
int lcIndex;
int rcIndex;
int temp = heap[index];
int largeChildIndex;
int smallChilIndex;
if (minMaxFlag == 0) {
while (index < (size / 2)) {
lcIndex = leftChildIndex(index);
rcIndex = rightChildIndex(index);
if (rcIndex < size && heap[lcIndex] < heap[rcIndex]) {
largeChildIndex = rcIndex;
} else {
largeChildIndex = lcIndex;
}
if (heap[largeChildIndex] <= temp)
break;
heap[index] = heap[largeChildIndex];
index = largeChildIndex;
}
} else {
while (index < (size / 2)) {
lcIndex = leftChildIndex(index);
rcIndex = rightChildIndex(index);
if (rcIndex < size && heap[lcIndex] > heap[rcIndex]) {
smallChilIndex = rcIndex;
} else {
smallChilIndex = lcIndex;
}
if (heap[smallChilIndex] >= temp)
break;
heap[index] = heap[smallChilIndex];
index = smallChilIndex;
}
}
heap[index] = temp;
}
}
```
Sample Output:-
Current median of 1 elements is: 1.0
Current median of 2 elements is: 1.5
Current median of 3 elements is: 2.0
Current median of 4 elements is: 2.5
Current median of 5 elements is: 3.0
Current median of 6 elements is: 3.5
Current median of 7 elements is: 4.0
Current median of 8 elements is: 4.5
Current median of 9 elements is: 5.0
Current median of 10 elements is: 5.5