A class to keep the median of an incoming stream of values.

median_keeper.cpp

template<typename T>
class MedianKeeper
{
public:
	
	double insert(const T& value)
	{
		if (is_empty() || value > _median)
		{
			_right.push(value);
			
			if (size() % 2 == 1) _median = _right.top();
			
			else _median = (_left.top() + _right.top()) / 2.0;
			
			if (_left.size() < _right.size())
			{
				_left.push(_right.top());
				
				_right.pop();
			}
		}
		
		else if (value < _median)
		{
			_left.push(value);
			
			if (size() % 2 == 1) _median = _left.top();
			
			else _median = (_left.top() + _right.top()) / 2.0;
			
			if (_right.size() < _left.size())
			{
				_right.push(_left.top());
				
				_left.pop();
			}
		}
		
		return _median;
	}
	
	double median() const
	{
		if (is_empty()) throw std::runtime_error("No median!");
		
		return _median;
	}
	
	
	void clear()
	{
		_left.clear();
		
		_right.clear();
	}
	
	
	size_t size() const
	{
		return _left.size() + _right.size();
	}
	
	bool is_empty() const
	{
		return _left.empty();
	}

	
private:
	
	double _median;
	
	std::priority_queue<T, std::vector<T>, std::greater<T>> _right;
	
	std::priority_queue<T> _left;
};

int main(int argc, const char* argv[])
{
	std::uniform_int_distribution<std::size_t> distribution(0, 10);
	
	std::random_device seed;
	
	std::mt19937 random(seed());
	
	std::vector<std::size_t> v(10);
	
	for (std::size_t i = 0; i < v.size(); ++i)
	{
		v[i] = distribution(random);
	}
	
	print::all(v);
	
	MedianKeeper<std::size_t> keeper;
	
	for (const auto& i : v)
	{
		std::cout << keeper.insert(i) << " ";
	}
}