Running median, moving median, continuous median, or median from the dynamic stream of integers are all the names for the same and well-known coding problem. You are given with dynamic stream of integers, coming one after another randomly and unsorted and you have to find the median of the current received set of integers.
The median is the "middle" value of a sorted set of numbers. To find the median, you must first sort your set of integers in non-decreasing order. Then, if there is:
odd number of integers, the middle element is the median. For example, in the ordered set:
2, 5, 6, 8, 10the median is
even number of integers, there's no middle element; the median is computed as the average of the two middle elements. Example in the ordered set:
3, 4, 7, 8, 10, 15the median is
(7 + 8) / 2 = 7.5.
We need to write a function to get a median number of dynamic stream. Let's think about the dynamic stream (running/moving/continuous) median as an array of numbers that you are reading in one after another and after each number you want to print the median of all numbers.
How we are going to do this?
One of the most effective ways of solving this is a Heap Data Structure.
A Heap is a special Tree-based data structure in which the tree is a complete binary tree. There are in general two types of heap Max-Heap and Min-Heap.
- The root node has the minimum value.
- The value of each node is equal to or greater than the value of its parent node.
- The root node has the maximum value.
- The value of each node is equal to or less than the value of its parent node.
Actually, the Heap approach is the perfect solution for our problem because it allows us to efficiently pull out the biggest element (maximum value) or smallest element (minimum value):
When a number comes we will first compare it with the current median and put it to the appropriate Heap. If the new integer value is less than the current median, we put it into the max-heap else we put it to the min-heap.
In Java, the
PriorityQueue class represents a heap. As per definition PriorityQueue in Java is a special type of queue wherein all the elements are ordered as per their natural ordering or based on a custom Comparator supplied at the time of creation. Let's divide the solution into 4 main steps.
That's going to take an integer array and return an array of doubles like this:
This method will look into two Heap sizes, if they are different take the top element from the larger Heap. If they are the same size we will need to average them:
Github repo can be found here.