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