Median of Dynamic Stream of Integers 
Tags: javascript, java, algorithms, tutorial
Published: 2021-02-28 04:40:09

# 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xj2ijrz3e16f8c4fb53x.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/z2kizk4kgrjw2464pd7x.png)
#### 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rj3iy2lvuhkgpi0ue1qs.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vi8hmw0mp1n4r7m363le.png)
 

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a04fk812gl7m4rjcyqly.png)

### STEP 2. `addNumber` method

that will take in number, `priorityQueue` of the lowers and highers like this:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/12sxvnfufxj0c42tf9uf.png)

### 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3mhobwvomr2evykuycq6.png)

### 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ofa07lp0v2wcwlfw93k6.png)


#### Thank you for reading!

Github repo can be found [here](https://github.com/ivanadokic/Median-Dynamic-Stream).
 
To connect with me please check my [Github](https://github.com/ivanadokic), [LinkedIn](https://www.linkedin.com/in/ivana-dokic/) or [Twitter](https://twitter.com/LloydPile).