Our goal is to find the median of all the elements read so far starting from the first integer till the last integer. This is also called the Median of Running Integers. The data stream can be any source of data, for example, a file, an array of integers, an input stream, etc.
But what is the median? Median can be defined as the element in the data set which separates the higher half of the data sample from the lower half. In other words, we can get the median element as, when the input size is odd, we take the middle element of sorted data. If the input size is even, we pick an average of the middle two elements in the sorted stream.
How can we find the median using algorithms? If we keep each number in a sorted sequence then the cost of a single entry is O(n) and the finding median is O(n). A slight modification can be done by keeping the middle pointer and adjusting it based on the insertion on its left side and right side. In that case, the finding median after insertion is O(1). But the overall cost for finding median remains O(n) as an insertion in the sorted sequence is necessary after each number is entered.
So which approach could we use to find the median more efficiently? There are several methods to find the median:
- Method 1: Insertion Sort
If we can sort the data as it appears, we can easily locate the median element. Insertion Sort is one such online algorithm that sorts the data appeared so far. At any instance of sorting, say after sorting i-th element, the first i elements of the array are sorted. The insertion sort doesn’t depend on future data to sort data input till that point. In other words, insertion sort considers data sorted so far while inserting the next element. This is the key part of insertion sort that makes it an online algorithm.
However, insertion sort takes O(n2) time to sort n elements. Perhaps we can use binary search on insertion sort to find the location of the next element in O(log n) time. Yet, we can’t do data movement in O(log n) time. No matter how efficient the implementation is, it takes polynomial time in case of insertion sort. - Method 2: Augmented self-balanced binary search tree (AVL, RB, etc…)
At every node of BST, maintain some elements in the subtree rooted at that node. We can use a node as the root of a simple binary tree, whose left child is self-balancing BST with elements less than root and right child is self-balancing BST with elements greater than root. The root element always holds the effective median.
If the left and right subtrees contain the same number of elements, the root node holds the average of left and right subtree root data. Otherwise, the root contains the same data as the root of subtree which is having more elements. After processing an incoming element, the left and right subtrees (BST) are differed utmost by 1.
Self-balancing BST is costly in managing the balancing factor of BST. However, they provide sorted data which we don’t need. We need median only. The next method makes use of Heaps to trace the median. - Method 3: Heaps
Similar to balancing BST in Method 2 above, we can use a max heap on the left side to represent elements that are less than the effective median, and a min-heap on the right side to represent elements that are greater than the effective median.
After processing an incoming element, the number of elements in heaps differs utmost by 1 element. When both heaps contain the same number of elements, we pick the average of heaps root data as the effective median. When the heaps are not balanced, we select the effective median from the root of the heap containing more elements.
Useful code:
// C# program to find med in// stream of running integersusing System;using System.Collections.Generic;public class MedianMaintain{// method to calculate med of streampublic static void printMedian(int[] a){ double med = a[0];// max heap to store the smaller half elementsList<int> smaller = new List<int>();// min-heap to store the greater half elementsList<int> greater = new List<int>(); smaller.Add(a[0]);Console.WriteLine(med);// reading elements of stream one by one/* At any time we try to make heaps balanced andtheir sizes differ by at-most 1. If heaps arebalanced,then we declare median as average ofmin_heap_right.top() and max_heap_left.top()If heaps are unbalanced,then median is definedas the top element of heap of larger size */for(int i = 1; i < a.Length; i++){int x = a[i];// case1(left side heap has more elements)if(smaller.Count > greater.Count){if(x < med){smaller.Sort();smaller.Reverse();greater.Add(smaller[0]);smaller.RemoveAt(0);smaller.Add(x);}elsegreater.Add(x);smaller.Sort();smaller.Reverse();greater.Sort();med = (double)(smaller[0] + greater[0])/2;}// case2(both heaps are balanced)else if(smaller.Count == greater.Count){if(x < med){smaller.Add(x);smaller.Sort();smaller.Reverse();med = (double)smaller[0];}else{greater.Add(x);greater.Sort();med = (double)greater[0];}}// case3(right side heap has more elements)else{if(x > med){greater.Sort();smaller.Add(greater[0]);greater.RemoveAt(0);greater.Add(x);}elsesmaller.Add(x);smaller.Sort();smaller.Reverse();med = (double)(smaller[0] + greater[0])/2;}Console.WriteLine(med);}}// Driver codepublic static void Main(String []args){// stream of integersint[] arr = new int[]{5, 15, 10, 20, 3};printMedian(arr);}}// This code is contributed by Rajput-Ji |
Output:
5
10
10
12.5
10
Complexity Analysis:
- Time Complexity: O(n log n).
Time Complexity to insert an element in min-heap is log n. So to insert n element is O( n log n). - Auxiliary Space: O(n).
The Space required to store the elements in Heap is O(n).
Demo:
Median of Stream of Running Integers using STL | GeeksforGeeks – YouTube
References
Median of Stream of Running Integers using STL – GeeksforGeeks
Data Structures and Algorithm: Running Median (dsalgo.com)
Median in a stream of integers (running integers) – GeeksforGeeks
Leave a Reply
Want to join the discussion?Feel free to contribute!