Finding the running median

Question

I have to find the running median as per this problem: https://www.hackerrank.com/challenges/ctci-find-the-running-median

I am trying to implement two heaps. A min heap which stores the elements lesser than the current median and a max heap which stores items greater than the current median.

The median keeps changing, and the difference in number of elements in both heaps does not exceed 1.

My code however is not being accepted. However it has passed test cases I could think of.

Please only read the main function and the update median function! Any help is appreciated.

#include<bits/stdc++.h>
#define pb push_back
using namespace std;

class max_heap{
private:
vector<int> items;
int size;

public:
max_heap(){
    size=0;
}
int left(int parent){   return (parent*2 + 1);  }
int right(int parent){  return (parent*2 + 2);  }
int parent(int pos){    return pos<=0 ? 0 : (pos-1)/2;      }
int getmax(){           return items[0];            }
int peek(int pos){  return items[pos];}
int length(){           return items.size();}


void swap(int pos1, int pos2){
    int tmp=items[pos1];
    items[pos1]=items[pos2];
    items[pos2]=tmp;
    return;
}
void insert(int key)
{

    if(items.size()==size)
        items.pb(key);
    else
        items[size]=key;

    //fixing items property
    int tmp=size;
    while(items[0]!=key && items[parent(tmp)] < key ){
        swap( parent(tmp), tmp);

        tmp=parent(tmp);
    }
    size++;

}

int pop(){

    if(size==0)
        return 0;
    int ans=getmax();
    size--;
    items[0]=items[size];

    //fix items
    int i=0;
    while(i<size-1){
        bool a = items[i] < items[right(i)];
        bool b = items[i] < items[left(i)];

        if( a && b)
        {
            if( items[left(i)] < items[right(i)] )
                swap(i,left(i));
            else swap(i,right(i));

        }
        else if(a)
            swap(i,right(i));
        else if(b)
            swap(i,left(i));
        else break;



    }
    return ans;
}

void print(){
    for (int i = 0; i < items.size(); ++i)
            cout<<items[i]<<" ";
    cout<<endl;
}
};

class min_heap{
private:
vector<int> items;
int size;

public:
min_heap(){
    size=0;
}
int left(int parent){   return (parent*2 + 1);  }
int right(int parent){  return (parent*2 + 2);  }
int parent(int pos){    return pos<=0 ? 0 : (pos-1)/2;      }
int getmin(){           return items[0];            }
int peek(int pos){  return items[pos];}
int length(){           return items.size();}


void swap(int pos1, int pos2){
    int tmp=items[pos1];
    items[pos1]=items[pos2];
    items[pos2]=tmp;
    return;
}
void insert(int key)
{

    if(items.size()==size)
        items.pb(key);
    else
        items[size]=key;

    //fixing items property
    int tmp=size;
    while(items[0]!=key && items[parent(tmp)] > key ){
        swap( parent(tmp), tmp);

        tmp=parent(tmp);
    }
    size++;

}

int pop(){

    if(size==0)
        return 0;
    int ans=getmin();
    size--;
    items[0]=items[size];

    //fix items
    int i=0;
    while(i<size-1){
        bool a = items[i] > items[right(i)];
        bool b = items[i] > items[left(i)];

        if( a && b)
        {
            if( items[left(i)] < items[right(i)] )
                swap(i,left(i));
            else swap(i,right(i));

        }
        else if(a)
            swap(i,right(i));
        else if(b)
            swap(i,left(i));
        else break;



    }
    return ans;
}

void print(){
    for (int i = 0; i < items.size(); ++i)
            cout<<items[i]<<" ";
    cout<<endl;
}
};

double update_median(int element, int median, min_heap &mn_heap, max_heap &mx_heap)
{

int path = mx_heap.length() - mn_heap.length();
    double ans=0.0;

switch(path){

    case 0:

    if( element >  median ){
        //push to right heap..ie the min heap
        mn_heap.insert(element);
        ans= mn_heap.getmin();
    }
    else
    {
        //push to left heap....ie max heap
        mx_heap.insert(element);
        ans= mx_heap.getmax();
    }

    break;

    case 1:     //max heap is greater ie left

    if( element >  median )
    {   //push to right heap...min heap

        mn_heap.insert(element);
        ans=(mn_heap.getmin() + mx_heap.getmax()) / 2.0;

    }

    else
    {
        mn_heap.insert(mx_heap.pop());
        mx_heap.insert(element);
        ans= (mn_heap.getmin() + mx_heap.getmax()) / 2.0;
    }

    break;


    case -1: // min heap greater ie right

    if( element >  median )
    {   //push to right heap...min heap

        mx_heap.insert(mn_heap.pop());
        mn_heap.insert(element);
        ans=(mn_heap.getmin() + mx_heap.getmax()) / 2.0;

    }

    else
    {

        mx_heap.insert(element);
        ans= (mn_heap.getmin() + mx_heap.getmax()) / 2.0;

    }

    break;




}

return ans;

}

int main(){

    cout.sync_with_stdio(false);
    int el;
    cin>>el;

    double median=0.0;

    min_heap *a = new min_heap(); //items less than median
    max_heap *b = new max_heap(); //items more than median


    while(el--){
        int element;
        cin>>element;

        median= update_median(element,median,*a,*b);

        printf("%.1lf\n", median);
    }
}

Answer 1

I think the problem is in the pop method of your max_heap implementation. You have:

    if( a && b)
    {
        if( items[left(i)] < items[right(i)] )
            swap(i,left(i));
        else swap(i,right(i));

    }

That always swaps the parent with the smaller of the two children. In a max heap you want to swap the parent with the larger of the two children. Your min_heap implementation also swaps the parent with the smaller of the two children, which is correct.

Answer 2

Find the Running Median using Java - Hackerrank Solution

package com.syed.test;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Solution {

    static double[] runningMedian(int[] a) {

        int[] temp = new int[a.length];
        double[] resultArray = new double[a.length];
        int counter = 0;

        for (int i = 0; i < a.length; i++) {
            temp[i] = a[i];
            counter++;

            if (i == 0) {
                resultArray[i] = (double) temp[i];
                System.out.println("i : " + i + "  " + Arrays.toString(temp));
            } else {

                Arrays.sort(temp, 0, i + 1);
                System.out.println("i : " + i + "  " + Arrays.toString(temp));

                int val = counter / 2;

                if (counter % 2 == 0)
                    resultArray[i] = (temp[val] + temp[val - 1]) / 2.0;
                else 
                    resultArray[i] = temp[val];
            }
        }
        System.out.println("\n Result Array : " + Arrays.toString(resultArray));
        return resultArray;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter("d://output.txt"));

        int aCount = Integer.parseInt(scanner.nextLine().trim());

        int[] a = new int[aCount];

        for (int aItr = 0; aItr < aCount; aItr++) {
            int aItem = Integer.parseInt(scanner.nextLine().trim());
            a[aItr] = aItem;
        }

        double[] result = runningMedian(a);

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

input:

6
12
4
5
3
8
7

output:

Result Array : [12.0, 8.0, 5.0, 4.5, 5.0, 6.0]