Question

How to find the running median from a stream of integers in C++

Answer 1

#include <iostream>
#include <queue>
#include <vector>
#include <iomanip>
#include <stdexcept>

/*
A running median (also called an online median) is the median value 
of a set of numbers that are received one at a time in a continuous stream.

Instead of waiting for all numbers to be available, we calculate 
and update the median after each new integer arrives.

Examples:

Numbers: 1, 3, 5
Median: 3

Numbers: 1, 3, 5, 7
Median: (3 + 5) / 2 = 4

| Stream So Far | Sorted Order | Median |
| ------------- | ------------ | ------ |
| 5             | 5            | 5      |
| 5, 15         | 5, 15        | 10     |
| 5, 15, 1      | 1, 5, 15     | 5      |
| 5, 15, 1, 3   | 1, 3, 5, 15  | 4      |


*/



class RunningMedian
{
public:
    // Adds a new number to the data stream.
    void addNumber(int value)
    {
        // Insert into the appropriate heap.
        if (lower_.empty() || value <= lower_.top()) {
            lower_.push(value);
        }
        else {
            upper_.push(value);
        }

        rebalanceHeaps();
    }

    // Returns the current median.
    double getMedian() const
    {
        if (lower_.empty() && upper_.empty()) {
            throw std::runtime_error("No elements in stream.");
        }

        if (lower_.size() == upper_.size()) {
            return (static_cast<double>(lower_.top()) +
                    static_cast<double>(upper_.top())) / 2.0;
        }

        return (lower_.size() > upper_.size())
                   ? static_cast<double>(lower_.top())
                   : static_cast<double>(upper_.top());
    }

private:
    // Max-heap for the lower half.
    std::priority_queue<int> lower_;

    // Min-heap for the upper half.
    std::priority_queue<
        int,
        std::vector<int>,
        std::greater<int>> upper_;

    // Ensures the heaps remain balanced.
    void rebalanceHeaps()
    {
        if (lower_.size() > upper_.size() + 1) {
            upper_.push(lower_.top());
            lower_.pop();
        }
        else if (upper_.size() > lower_.size() + 1) {
            lower_.push(upper_.top());
            upper_.pop();
        }
    }
};

int main()
{
    RunningMedian medianTracker;

    std::vector<int> stream = {
        5, 15, 1, 3, 8, 7, 9, 10, 6
    };

    std::cout << std::fixed << std::setprecision(1);

    for (int value : stream)
    {
        medianTracker.addNumber(value);

        std::cout << "Inserted: " << value
                  << ", Running Median: "
                  << medianTracker.getMedian()
                  << '\n';
    }
}


/*
run:

Inserted: 5, Running Median: 5.0
Inserted: 15, Running Median: 10.0
Inserted: 1, Running Median: 5.0
Inserted: 3, Running Median: 4.0
Inserted: 8, Running Median: 5.0
Inserted: 7, Running Median: 6.0
Inserted: 9, Running Median: 7.0
Inserted: 10, Running Median: 7.5
Inserted: 6, Running Median: 7.0

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

/*
A running median (also called an online median) is the median value 
of a set of numbers that are received one at a time in a continuous stream.

Instead of waiting for all numbers to be available, we calculate 
and update the median after each new integer arrives.

Examples:

Numbers: 1, 3, 5
Median: 3

Numbers: 1, 3, 5, 7
Median: (3 + 5) / 2 = 4

*/

// Adds a number and returns the current median.

// Adds a number to the data stream and returns the current median.
double addAndGetMedian(
    int value,
    std::priority_queue<int>& lowerHalf,
    std::priority_queue<
        int,
        std::vector<int>,
        std::greater<int>>& upperHalf)
{
    // Insert into the appropriate heap.
    if (lowerHalf.empty() || value <= lowerHalf.top()) {
        lowerHalf.push(value);
    }
    else {
        upperHalf.push(value);
    }

    // Rebalance the heaps so their sizes differ by at most one.
    if (lowerHalf.size() > upperHalf.size() + 1) {
        upperHalf.push(lowerHalf.top());
        lowerHalf.pop();
    }
    else if (upperHalf.size() > lowerHalf.size() + 1) {
        lowerHalf.push(upperHalf.top());
        upperHalf.pop();
    }

    // Calculate and return the median.
    if (lowerHalf.size() == upperHalf.size()) {
        return (static_cast<double>(lowerHalf.top()) +
                static_cast<double>(upperHalf.top())) / 2.0;
    }

    return (lowerHalf.size() > upperHalf.size())
               ? static_cast<double>(lowerHalf.top())
               : static_cast<double>(upperHalf.top());
}

int main()
{
    const std::vector<int> stream = {5, 15, 1, 3, 8, 7, 9, 10, 6};

    // Max heap storing the lower half of the numbers.
    std::priority_queue<int> lowerHalf;

    // Min heap storing the upper half of the numbers.
    std::priority_queue<
        int,
        std::vector<int>,
        std::greater<int>> upperHalf;

    for (int value : stream) {
        const double median =
            addAndGetMedian(value, lowerHalf, upperHalf);

        std::cout << "Inserted: " << value
                  << ", Median: " << median
                  << '\n';
    }
}


/*
run:

Inserted: 5, Median: 5
Inserted: 15, Median: 10
Inserted: 1, Median: 5
Inserted: 3, Median: 4
Inserted: 8, Median: 5
Inserted: 7, Median: 6
Inserted: 9, Median: 7
Inserted: 10, Median: 7.5
Inserted: 6, Median: 7

*/

 

70+ SQL courses for beginners and professionals