DEV Community

loading...
Cover image for Median of Dynamic Stream of Integers

Median of Dynamic Stream of Integers

ivanadokic profile image Ivana ・3 min read

Introduction

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.

1. Let's first define what is median

Alt Text

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, 10 the median is 6.
  • 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, 15 the median is (7 + 8) / 2 = 7.5.

2. Formalize the dynamic stream statement

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?

3. Heap Data Structure

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.

Alt Text

In a Min-Heap:

  1. The root node has the minimum value.
  2. The value of each node is equal to or greater than the value of its parent node.

In a Max-Heap:

  1. The root node has the maximum value.
  2. The value of each node is equal to or less than the value of its parent node.

Alt Text

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):

Alt Text

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.

4. Let's turn to the code

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.

STEP 1. getMedians function

That's going to take an integer array and return an array of doubles like this:

Alt Text

STEP 2. addNumber method

that will take in number, priorityQueue of the lowers and highers like this:
Alt Text

STEP 3. rebalance method

Rebalancing works by moving the largest element from the max-heap to the min-heap, or by moving the smallest element from the min-heap to the max-heap:
Alt Text

STEP 4. getMedian method

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:

Alt Text

Thank you for reading!

Github repo can be found here.

To connect with me please check my Github, LinkedIn or Twitter.

Discussion (0)

pic
Editor guide