We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Heaps: Find the Running Median
  2. Discussions

Heaps: Find the Running Median

  • thomas_fischle
     + 0 comments

    Using a multiset and moving iterator to median left/right.

    `
void runningMedian(vector<int> arr) {
    // Print your answer within the function
    std::cout << std::fixed;
    std::cout << std::setprecision(1);
    
    std::multiset<int> ms;
    float median = 0.0;
    
    cout << float(arr[0]) << endl;
    ms.insert(arr[0]);
    std::multiset<int>::iterator med = ms.begin();
    
    for(size_t cs = 1; cs < arr.size(); cs++)
    {
       ms.insert(arr[cs]);
        // odd,
        if(cs % 2 == 0){
            if(arr[cs] >= *med) med = next(med, 1);
            median = *med;
        }
        //even
       else{
           if(arr[cs] < *med) med = next(med, -1);
            median = (*med + *(std::next(med, 1)))/ 2.0;
       }
       cout << float(median) << endl; 
    }
}