Median Of Stream Of Running Integers in Java

An integer array is given to us. Compute the median of the elements traversed so far in the input array. For the sake of simplicity, assume that there are no duplicates.

Example:

Input

int arr[] = {17, 11, 15, 13, 10, 12, 18, 19, 1, 16, 14, 20};

Output: {17, 14, 15, 14, 13, 12, 13, 14, 13, 14, 14, 14.5}

Explanation: We start reading the array from left to right. The first element traversed is 17. Hence, the median is 17. It is because only one element is traversed. After that, element 11 is traversed. Now, at this point, we have traversed two elements 17 and 11. Thus, the median becomes (11 + 17) / 2 = 14.

After that, element 15 is traversed. Now we have a total of 3 elements traversed, 17, 11, and 15, and the median of an odd number of elements is the middle element when the elements are arranged in ascending order. Thus, the median of those three elements is {11, 15, 17} => {15}.

Now, element 13 comes into the picture, and a total of 4 elements are traversed, and the median of the even number of elements is the average of the two middle elements when the elements are sorted. Thus, the current median is: {11, 13, 15, 17} => (13 + 15) / 2 = 14. Similarly, we can compute the other medians too.

Approach: Using Insertion Sort

It is evident from the above example that for computing the median. It is required to sort the integers that are traversed till now. Therefore, we need a sorting technique to sort the elements. We will be using insertion sort to sort the elements.

FileName: RunningIntegerStream.java

public class RunningIntegerStream 
{


// Method that finds the position for inserting the current element 
// into the stream with the help of binary search.
static int binarySearch(int inputArr[], int ele, int l, int h)
{
if (l >= h) 
{
return (ele > inputArr[l]) ? (l + 1) : l;
}


int midIndex = (l + h) / 2;


if (ele == inputArr[midIndex])
{
return midIndex + 1;
}


// recursively finding the appropriate index for the element ele
if (ele > inputArr[midIndex])
{
return binarySearch(inputArr, ele, midIndex + 1, h);
}


return binarySearch(inputArr, ele, l, midIndex - 1);
}


// Method that displays the median of running or stream integers
public void displayMedian(int inputArr[], int s)
{
int a, b, position, number;
int countEle = 1;


System.out.println("Median after reading element " + inputArr[0] + " is: " + inputArr[0]);


for (a = 1; a < s; a++) 
{
float median;
b = a - 1;
number = inputArr[a];


// find the position to insert the current element in sorted
// part of the array
position = binarySearch(inputArr, number, 0, b);


// move elements to the right to create space to insert
// the current element
while (b >= position) 
{
inputArr[b + 1] = inputArr[b];
b = b - 1;
}


inputArr[b + 1] = number;


// increment count of sorted elements in the array
countEle = countEle + 1;


// if we have traversed only the odd number of elements, then
// the median is the middle element when the elements are sorted.
// else the median is an average of two middle elements.


if (countEle % 2 != 0) 
{
median = inputArr[countEle / 2];
}
else 
{
median = (float)(inputArr[(countEle / 2) - 1] + (float)inputArr[countEle / 2]) / 2f;
}
System.out.print( "Median after reading { ");
for(int i = 0; i < a + 1; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.println( "} elements is " + median );
}
}




// main method
public static void main (String[] argvs) 
{
// creating an object of the class RunningIntegerStream
RunningIntegerStream obj = new RunningIntegerStream();
int inputArr[] = { 17, 11, 15, 13, 10, 12, 18, 19, 1, 16, 14, 20 };
int s = inputArr.length;


// invoking the method displayMedian
obj.displayMedian(inputArr, s);
}
}

Output:

Median after reading element 17 is: 17
Median after reading { 11 17 } elements is 14.0
Median after reading { 11 15 17 } elements is 15.0
Median after reading { 11 13 15 17 } elements is 14.0
Median after reading { 10 11 13 15 17 } elements is 13.0
Median after reading { 10 11 12 13 15 17 } elements is 12.5
Median after reading { 10 11 12 13 15 17 18 } elements is 13.0
Median after reading { 10 11 12 13 15 17 18 19 } elements is 14.0
Median after reading { 1 10 11 12 13 15 17 18 19 } elements is 13.0
Median after reading { 1 10 11 12 13 15 16 17 18 19 } elements is 14.0
Median after reading { 1 10 11 12 13 14 15 16 17 18 19 } elements is 14.0
Median after reading { 1 10 11 12 13 14 15 16 17 18 19 20 } elements is 14.5

Complexity Analysis: The program uses insertion sort technique. Thus, the time complexity of the program is O(n²). The program is not using any data structure. Hence, the space complexity of the program is constant, i.e., O(1).

Note: One may argue why the insertion sort technique has been used in the program. One can also use other sorting techniques too, like selection sort, merge sort etc. The reason behind this is that at any given instance of insertion sorting, say doing sorting of the kth element, the first k elements of the input array are sorted. The insertion sort does not depend on the data that are coming next (future data) to sort the data present till that point. In other words, insertion sort does data sorting so far while the next element is inserted. It is the important aspect of the insertion sort that makes this algorithm an online algorithm.

Approach: Using AVL Tree

Using the AVL tree, one can find the median of the running integers. One by one, we will be inserting the elements in the AVL tree and will also keep track of the

FileName: RunningIntegerStream1.java

class TreeNode 
{
int key;
int freq; // the number of times an element occurs in the stream
int lSubTreeCount; // total number of nodes present in the in the left subtree
int rSubTreeCount; // total number of nodes present in the right subtree
int hght; // height for doing the AVL operations
TreeNode lft;
TreeNode rght;


TreeNode(int key) 
{
this.key = key;
hght = 1;
lft = rght = null;
lSubTreeCount = rSubTreeCount = 0;
freq = 1;
}
}


class AVL 
{
TreeNode root;
int size;


AVL() {
size = 0;
root = null;
}


void insert(int key) {
root = insertHelper(root, key);
}


TreeNode leftR(TreeNode x) 
{
TreeNode y = x.rght;
TreeNode T = y.lft;


// Performing the rotation
y.lft = x;
x.rght = T;


// Updating the heights
x.hght = Math.max(findHeight(x.lft), findHeight(x.rght)) + 1;
y.hght = Math.max(findHeight(y.lft), findHeight(y.rght)) + 1;


// updating the count
x.rSubTreeCount = (T != null) ? T.lSubTreeCount + T.rSubTreeCount + T.freq : 0;
y.lSubTreeCount = x.lSubTreeCount + x.rSubTreeCount + x.freq;


// Return new root
return y;
}


TreeNode rightR(TreeNode y) 
{
TreeNode x = y.lft;
TreeNode T = x.rght;


// Performing the rotation
x.rght = y;
y.lft = T;


// Update heights
y.hght = Math.max(findHeight(y.lft), findHeight(y.rght)) + 1;
x.hght = Math.max(findHeight(x.lft), findHeight(x.rght)) + 1;


// updating the count
y.lSubTreeCount = (T != null) ? T.lSubTreeCount + T.rSubTreeCount +T.freq : 0;
x.rSubTreeCount = y.lSubTreeCount + y.rSubTreeCount + y.freq;


// Returning the new root
return x;
}


// finding the difference in heights between the 
// left and the right subtrees
int findBalance(TreeNode root) 
{
if (root == null)
{
return 0;
}
return findHeight(root.lft) - findHeight(root.rght);
}


// finding the height of the tree
int findHeight(TreeNode root) 
{
if (root == null)
{
return 0;
}
return root.hght;
}


TreeNode insertHelper(TreeNode root, int key) 
{
// inserting the key into the tree
// incrementing the size
if (root == null) 
{
size = size + 1;
return new TreeNode(key);
}


if (key < root.key) 
{
root.lft = insertHelper(root.lft, key);
root.lSubTreeCount++;
}


else if (key > root.key) 
{
root.rght = insertHelper(root.rght, key);
root.rSubTreeCount++;
}


else {
root.freq++;
size = size + 1;
return root;
}


// insertion is done, update the height and check for balancing factor
root.hght = 1 + Math.max(findHeight(root.lft), findHeight(root.rght));


int balance = findBalance(root);


// If the node is getting unbalanced, then there
// are following four cases 


// Left Left Case
if (balance > 1 && key < root.lft.key)
{
return rightR(root);
}


// Right Right Case
if (balance < -1 && key > root.rght.key)
{
return leftR(root);
}


// Left Right Case
if (balance > 1 && key > root.lft.key) 
{
root.lft = leftR(root.lft);
return rightR(root);
}


// Right Left Case
if (balance < -1 && key < root.rght.key) 
{
root.rght = rightR(root.rght);
return leftR(root);
}


// returning the unchanged node pointer that is unchanged
return root;


}


float findMedian() 
{
// as per the size (either even or odd) look for the element(s) that are required to find
// out the median
int indx = size / 2 + 1;
int k1 = 0; 
int k2 = 0;
float medianVal = 0;


k1 = findEle(root, indx);
medianVal = k1 / 1.0f;
if (size % 2 == 0) 
{
k2 = findEle(root, indx - 1);
medianVal = (k1 + k2) / 2.0f;
}
return medianVal;
}


int findEle(TreeNode root, int indx) 
{


if (indx >= root.lSubTreeCount + 1  && indx < root.lSubTreeCount + 1 + root.freq)
{
return root.key;
}


else if (indx <= root.lSubTreeCount)
{
return findEle(root.lft, indx);
}


else
{
return findEle(root.rght, indx - root.lSubTreeCount - root.freq);
}
}




}


public class RunningIntegerStream1 
{


// Method that displays the median of running or stream integers
public void displayMedian(int inputArr[], int s)
{
int a, b, position, number;
int countEle = 1;


System.out.println("Median after reading element " + inputArr[0] + " is: " + inputArr[0]);


AVL avl = new AVL();


avl.insert(inputArr[0]);


for (a = 1; a < s; a++) 
{
float median;
avl.insert(inputArr[a]);
median = avl.findMedian();


System.out.print( "Median after reading { ");
for(int i = 0; i < a + 1; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.println( "} elements is " + median );
}
}


// main method
public static void main (String[] argvs) 
{
// creating an object of the class RunningIntegerStream1
RunningIntegerStream1 obj = new RunningIntegerStream1();
int inputArr[] = { 17, 11, 15, 13, 10, 12, 18, 19, 1, 16, 14, 20 };
int s = inputArr.length;


// invoking the method displayMedian
obj.displayMedian(inputArr, s);
}
}

Output:

Median after reading element 17 is: 17
Median after reading { 17 11 } elements is 14.0
Median after reading { 17 11 15 } elements is 15.0
Median after reading { 17 11 15 13 } elements is 14.0
Median after reading { 17 11 15 13 10 } elements is 13.0
Median after reading { 17 11 15 13 10 12 } elements is 12.5
Median after reading { 17 11 15 13 10 12 18 } elements is 13.0
Median after reading { 17 11 15 13 10 12 18 19 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 1 } elements is 13.0
Median after reading { 17 11 15 13 10 12 18 19 1 16 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 1 16 14 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 1 16 14 20 } elements is 14.5

Complexity Analysis: In an AVL tree, the time complexity of inserting an element is O(log(n). Therefore, the overall time complexity of the program is O(n x log(n)). The program allocates memories for the nodes of the AVL tree. Therefore, the space complexity of the program is O(n), where n is the total number of running integers that have been traversed.

Approach: Using Min and Max Heap

The concept is for keeping the min heap and max heap for keeping the elements of the lower half and the higher half. The min heap and max heap in Java can be implemented with the help of PriorityQueue. The following steps are required to solve the problem.

Algorithm:

Step 1: Create two heaps: one for the max heap for maintaining elements of the lower half and another one for the min heap for maintaining elements of the higher half at any given point in time.

Step 2: Initialize the value of the median as 0.

Step 3: For every currently read element, insert it either into the min heap or max heap and compute the median with the help of the following conditions:

• If the max heap size is more than the min heap size and the element is not more than the previous median, then remove the element from the top of the max heap and put it into the min heap and put the new element into the max heap. Otherwise, put the new element into the min heap. Compute the current median as the sum of the top of elements from both the min and the max heap divided by 2.
• If the max heap size is less than the min heap size and the element is larger than the previous median, then remove the element at the top from the min heap and put it into the max heap and put the new element in to the min heap. Otherwise, put the new element in to the max heap. Compute the current median as the sum of the top of elements from both the min and the max heap divided by 2.
• If the size is the same for both the heaps, then check whether the current element is less than the previous median or not. If yes, then insert the current element into the max heap, and the element at the top of the max heap is our current median. If no, then insert the current element into the min heap, and the element at the top of the min heap is our current median.

FileName: DisplayLeafBST1.java

// import statements required in the program
import java.util.PriorityQueue;
import java.util.Collections;


public class RunningIntegerStream 
{


// Method that displays the median of running or stream integers
public void displayMedian(int inputArr[], int s)
{


float median = inputArr[0];


// max heap for keeping the smaller half elements 
PriorityQueue<Integer> smallerPQ = new PriorityQueue<>
(Collections.reverseOrder());


// minimum heap for keeping the greater half of elements 
PriorityQueue<Integer> greaterPQ = new PriorityQueue<>();


smallerPQ.add(inputArr[0]);
System.out.println("Median after reading element " + inputArr[0] + " is: " + inputArr[0]);


// one by one traversing elements of the stream 
// At any given time, we try to balance the heaps and 
// at most difference in their sizes is 1. If heaps are 
// balanced, then the median is the average of 
// the minHeapRight.top() and the maxHeapLeft.top() 
// If the heaps are unbalanced, then the median is defined 
// as the element at the top of heap of the greater size 
for(int j = 1; j < s; j++)
{
int size1 = smallerPQ.size();
int size2 = greaterPQ.size();
int y = inputArr[j];


// case 1 (the left-side heap has the more number of elements) 
if(size1 > size2)
{
if(y < median)
{
greaterPQ.add(smallerPQ.remove());
smallerPQ.add(y);
}
else
greaterPQ.add(y);
median = (float)(smallerPQ.peek() + greaterPQ.peek())/2f;
}


// case 2 (both heaps are balanced) 
else if(size1 == size2)
{
if(y < median)
{
smallerPQ.add(y);
median = (float)smallerPQ.peek();
}
else
{
greaterPQ.add(y);
median = (float)greaterPQ.peek();
}
}


// case 3 (the right side heap has the more elements) 
else
{
if(y > median)
{
smallerPQ.add(greaterPQ.remove());
greaterPQ.add(y);
}
else
smallerPQ.add(y);
median = (float)(smallerPQ.peek() + greaterPQ.peek()) / 2f;


}
System.out.print( "Median after reading { ");
for(int i = 0; i < j; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.println( "} elements is " + median );
}


}




// main method
public static void main (String[] argvs) 
{
// creating an object of the class RunningIntegerStream
RunningIntegerStream obj = new RunningIntegerStream();
int inputArr[] = { 17, 11, 15, 13, 10, 12, 18, 19, 1, 16, 14, 20 };
int s = inputArr.length;


// invoking the method displayMedian
obj.displayMedian(inputArr, s);
}
}

Output:

Median after reading element 17 is: 17
Median after reading { 17 } elements is 14.0
Median after reading { 17 11 } elements is 15.0
Median after reading { 17 11 15 } elements is 14.0
Median after reading { 17 11 15 13 } elements is 13.0
Median after reading { 17 11 15 13 10 } elements is 12.5
Median after reading { 17 11 15 13 10 12 } elements is 13.0
Median after reading { 17 11 15 13 10 12 18 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 } elements is 13.0
Median after reading { 17 11 15 13 10 12 18 19 1 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 1 16 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 1 16 14 } elements is 14.5

Complexity Analysis: The time, as well as space complexity of the program, is the same as the previous program.