Printing the median of a stream of integers.

Problem

Given a stream of integers, print out the median of the stream at each time step.
Example input:
1, 2, 3, 4, 5
Example output:
1, 1.5, 2, 2.5, 3

Solution

This solution is in C++. Our A.I. can create solutions in multiple languages.

kayakane

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

using namespace std;

class MedianFinder {
public:
    MedianFinder() {
        // initialize your data structure here.
    }

    // Adds a number into the data structure.
    void addNum(int num) {
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }

        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        } else {
            return maxHeap.top();
        }
    }

private:
    priority_queue<int, vector<int>, less<int>> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
};

int main() {
    MedianFinder mf;
    mf.addNum(1);
    cout << mf.findMedian() << endl;
    mf.addNum(2);
    cout << mf.findMedian() << endl;
    mf.addNum(3);
    cout << mf.findMedian() << endl;
    mf.addNum(4);
    cout << mf.findMedian() << endl;
    mf.addNum(5);
    cout << mf.findMedian() << endl;
    return 0;
}