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

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

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

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.