题目：如何得到一个数据流中的中位数？

思路：

如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数，那么那么中位数就是排序之后中间两个数的平均值。

我们可以将整个数据分成两部分，分别用两个数据容器存储。如果能保证数据容器左边的数据都小于右边的数据，那么即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。我们可以用最大堆来实现左边的数据容器，因为位于堆顶的就是最大的数据。同样，也可以用最小堆来实现右边的数据容器。

往堆中插入一个数据的时间效率是O(logn)。由于只需要O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间复杂度是O(1)。

代码细节：

首先要保证数据平均分配到两个堆中，因此两个堆中数据的数目之差不能超过1。为了实现平均分配，可以在数据的总数目是偶数时把新数据插入最小堆，否则插入最大堆。

为了防止偶数时插入最小堆的数据比最大堆的一些数据小，我们可以先把这个数据插入最大堆，接着把最大堆中最大的数字拿出来插入最小堆。奇数时同理。

我们用STL中的函数push_heap、pop_heap以及vector实现堆。比较仿函数less和greater分别用来实现最大堆和最小堆。

template<typename T> class DynamicArray
{
public:
	void Insert(T num)
	{
		if(((min.size() + max.size()) & 1) == 0)
		{
			if(min.size() > 0 && num < max[0])
			{
				max.push_back(num);
				push_heap(max.begin(),max.end(),less<T>());

				num = max[0];
	
				pop_heap(max.begin(),max.end(),less<T>());
				max.pop_back();
			}
		
		
			min.push_back(num);
			push_heap(min.begin(),min.end(),greater<T>());
		}
		else
		{
			if(min.size() > 0 && min[0] < num)
			{
				min.push_back(num);
				push_heap(min.begin(),min.end(),greater<T>());
				
				num = min[0];
	
				pop_heap(min.begin(),min.end(),greater<T>());
				min.pop_back();
			}
			max.push_back(num);
			push_heap(max.begin(),max.end(),less<T>());
		}
	}

	T GetMeidan()
	{
		int size = min.size() + max.size();
		if(size == 0)
			throw exception("No numbers are availabel");
		
		T median = 0;
		if((size & 1) == 1)
			median = min[0];
		else
			median = (min[0] + max[0]) / 2;

		return median;
	}

private:
	vector<T>min;
	vector<T>max;
};