# HackerRank Find the Running Median problem solution

In this HackerRank Find the Running Median problem we have given an input stream of n integers, and we need to add the integer to a running list of integers. and then we need to find the median of the updated list and then print the updated median on the new line.

## Problem solution in Python programming.

```from heapq import *
under = []
upper = []
N = int(input())
for _ in range(N):
curNumber = int(input())
if (len(upper) == 0):
upper.append(curNumber)
print(curNumber)
continue
middle = upper[0]
if curNumber >= middle:
heappush(upper,curNumber)
else:
heappush(under, -curNumber)
if len(under) >= len(upper):
heappush(upper, -heappop(under))
if len(upper) >= len(under) + 2:
heappush(under, -heappop(upper))
if (len(upper) + len(under)) % 2 == 1:
print(float(upper[0]))
else:
print((float(upper[0]) + -under[0])/2)```

## Problem solution in Java Programming.

```import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {

public static void main(String[] args) {
try (Scanner in = new Scanner(System.in)) {

int n = in.nextInt();

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

for (int i = 0; i < n; ++i) {
int v = in.nextInt();
if (maxHeap.isEmpty() || (v < maxHeap.peek())) {
maxHeap.offer(v);
} else {
minHeap.offer(v);
}

if (maxHeap.size() > (minHeap.size() + 1)) {
minHeap.offer(maxHeap.poll());
}

if (minHeap.size() > (maxHeap.size() + 1)) {
maxHeap.offer(minHeap.poll());
}

if (maxHeap.size() > minHeap.size()) {
System.out.println(maxHeap.peek());
} else if (minHeap.size() > maxHeap.size()) {
System.out.println(minHeap.peek());
} else {
System.out.println(0.5 * (minHeap.peek() + maxHeap.peek()));
}
}

}
}
}```

## Problem solution in C++ programming.

```#include <set>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int N;
multiset<int> r;
multiset<int, greater<int> > l;
int main() {
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
int a; scanf("%d", &a);
if (l.empty()) l.insert(a);
else {
if (a > *l.begin()) r.insert(a);
else l.insert(a);
}
if (l.size() > r.size() + 1) {
r.insert(*l.begin());
l.erase(l.begin());
} else if (r.size() > l.size()) {
l.insert(*r.begin());
r.erase(r.begin());
}
if (l.size() > r.size())
printf("%d.0\n", *l.begin());
else
printf("%d.%c\n", (*l.begin() + *r.begin()) / 2, ((*l.begin() + *r.begin()) & 1) ? '5': '0');
}
return 0;
}```

## Problem solution in C programming.

```#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct {
int *array;
int count;
int size;
} Heap;

void heap_init(Heap *heap, int size) {
heap->size = size;
heap->array = (int *)malloc(size*sizeof(int));
heap->count = 0;
}

void minheap_push(Heap *heap, int x) {
assert(heap->count < heap->size);
int i = heap->count;
int p = (i-1)/2;
while (i > 0 && x < heap->array[p]) {
heap->array[i] = heap->array[p];
i = p;
p = (i-1)/2;
}
heap->array[i] = x;
heap->count++;
}

void maxheap_push(Heap *heap, int x) {
assert(heap->count < heap->size);
int i = heap->count;
int p = (i-1)/2;
while (i > 0 && x > heap->array[p]) {
heap->array[i] = heap->array[p];
i = p;
p = (i-1)/2;
}
heap->array[i] = x;
heap->count++;
}

int minheap_pop(Heap *heap) {
assert(heap->count > 0);
int result = heap->array[0];
int x = heap->array[--heap->count];
int next, i = 0;
while (1) {
int left = 2*i + 1;
int right = left + 1;
if (left >= heap->count) break;
if (heap->array[left] < x) {
if (right < heap->count && heap->array[right] < heap->array[left]) {
next = right;
} else {
next = left;
}
} else if (right < heap->count && heap->array[right] < x) {
next = right;
} else {
break;
}
heap->array[i] = heap->array[next];
i = next;
}
heap->array[i] = x;
return result;
}

int maxheap_pop(Heap *heap) {
assert(heap->count > 0);
int result = heap->array[0];
int x = heap->array[--heap->count];
int next, i = 0;
while (1) {
int left = 2*i + 1;
int right = left + 1;
if (left >= heap->count) break;
if (heap->array[left] > x) {
if (right < heap->count && heap->array[right] > heap->array[left]) {
next = right;
} else {
next = left;
}
} else if (right < heap->count && heap->array[right] > x) {
next = right;
} else {
break;
}
heap->array[i] = heap->array[next];
i = next;
}
heap->array[i] = x;
return result;
}

int main(void) {
int n, x;
scanf("%d", &n);

int size = n/2 + 2;
Heap minheap, maxheap;
heap_init(&minheap, size);
heap_init(&maxheap, size);

for (int i = 0; i < n; i++) {
scanf("%d", &x);

// Decide which heap x should go on.
if (minheap.count == 0) {
minheap_push(&minheap, x);
} else if (x > minheap.array[0]) {
minheap_push(&minheap, x);
} else {
maxheap_push(&maxheap, x);
}

// Then adjust sizes of heaps until they differ by at most 1.
while (minheap.count - maxheap.count > 1) {
int x = minheap_pop(&minheap);
maxheap_push(&maxheap, x);
}
while (maxheap.count - minheap.count > 1) {
int x = maxheap_pop(&maxheap);
minheap_push(&minheap, x);
}

float median;
if (minheap.count == maxheap.count) {
median = 0.5*(minheap.array[0] + maxheap.array[0]);
} else if (minheap.count > maxheap.count) {
median = minheap.array[0];
} else {
median = maxheap.array[0];
}
printf("%.1f\n", median);
}
return 0;
}```

## Problem solution in JavaScript programming.

```function processData(input) {
var inputArray = input.split('\n');
var testCase = parseInt(inputArray[0]);
var output=[], median=0;
var minHeap = function(){
this.myHeap = [];
this.getSize = function(){
return this.myHeap.length;
};
this.swap = function(i, j){             // swap;
var temp;
temp = this.myHeap[i];
this.myHeap[i] = this.myHeap[j];
this.myHeap[j] = temp;

};
this.bubble = function(i){
var pi = Math.floor(i/2);  // parent's index
if(this.myHeap[i] < this.myHeap[pi]){
this.swap(i, pi);
this.bubble(pi);
}
};
this.bubble_down = function(i){
var ci;
if(i==0){
ci = (this.myHeap[1] > this.myHeap[2]) ? 2: 1;  // child index choose small one
}else{
ci = (this.myHeap[i*2] > this.myHeap[i*2 +1]) ? i*2+1: i*2;  // child index choose small one
}

if(this.myHeap[ci]<this.myHeap[i]){
this.swap(ci, i);
this.bubble_down(ci)
}
};
this.myHeap.push(n);
this.bubble(this.myHeap.length-1);
};
this.peakMin = function(){
return this.myHeap[0];
}
this.getMin = function(){
this.swap(0, this.myHeap.length-1);
var min= this.myHeap.pop();
this.bubble_down(0);
return min;
}
};
var maxHeap = function(){
this.myHeap = [];
this.getSize = function(){
return this.myHeap.length;
};
this.swap = function(i, j){             // swap;
var temp;
temp = this.myHeap[i];
this.myHeap[i] = this.myHeap[j];
this.myHeap[j] = temp;

};
this.bubble = function(i){
var pi = Math.floor(i/2);  // parent's index
if(this.myHeap[i] > this.myHeap[pi]){
this.swap(i, pi);
this.bubble(pi);
}
};
this.bubble_down = function(i){
var ci;
if(i===0){
ci = (this.myHeap[1] < this.myHeap[2]) ? 2:1;
}
else{
ci = (this.myHeap[i*2] < this.myHeap[i*2 +1]) ? i*2+1: i*2;  // child index choose big one
}

if(this.myHeap[ci]>this.myHeap[i]){
this.swap(ci, i);
this.bubble_down(ci)
}
};
this.myHeap.push(n);
this.bubble(this.myHeap.length-1);
};
this.peakMax = function(){
return this.myHeap[0];
};
this.getMax = function(){
this.swap(0, this.myHeap.length-1);
var max=this.myHeap.pop();
this.bubble_down(0);
return max;
}
};
var minNode = new minHeap();           // keep it default -
var maxNode = new maxHeap();
var current,  smallmax, bigmin;
current = parseInt(inputArray[1]);
median = current;
output.push(median.toFixed(1));
for(var i=2; i<=testCase;i++) {
current = parseInt(inputArray[i]);

if( current < median ){
//prev = maxNode.getMax();
if (maxNode.getSize() == minNode.getSize()+1) {
median = maxNode.peakMax();
}else if (maxNode.getSize() > minNode.getSize()+1) {
smallmax = maxNode.getMax();
bigmin = smallmax;
smallmax= maxNode.peakMax();
median = (bigmin + smallmax)/2;
}
}else{
if(maxNode.getSize() == minNode.getSize()) {
median = ( maxNode.peakMax() + minNode.peakMin() ) / 2;
}else if (maxNode.getSize() < minNode.getSize()) {
bigmin= minNode.getMin();
median = bigmin;
}
}
output.push(median.toFixed(1));
}

console.log(output.join('\n'));
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
processData(_input);
});```