剑指offer（C++）——数据流中的中位数

题目描述

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

思路：由于数据是从数据流中读取出来的，数据的个数随着时间的变化而增加。因此我们需要一个数据容器来保存读取出来的数据。

解法1：用数组来保存数据。如果数组无序，则找到中位数最优的算法时间复杂度为O(n)，插入一个数字的时间复杂度为O(1)；

解法2：还可以让数组一直保持有序，有可能需要移动O(n)个数，因此插入一个数字的时间复杂度为O(n)，找到中位数只需O(1)时间即可完成；

解法3：用排序的链表来保存数据。插入一个数字需要O(n)时间，如果定义两个指针指向链表中间的结点，找到中位数只需O(1)时间；

解法4：用二叉搜索树保存数据。插入和查找中位数平均时间可以做到log(n)，最坏情况下同样需要O(n)时间；

解法5：用AVL树。稍微修改可以做到用O(logn)时间插入一个数字，O(1)时间得到中位数；

如果数据在容器中已经排好序，那么中位数可以有P1和P2指向的数得到。如果数据个数为奇数个，则P1和P2指向同一个数。

通过观察发现，整儿数据容器被分隔成两部分，位于容器左边的数比右边的数小，而且，P1指向的数据是左边部分最大数，P2指向的数据是右边部分最小数。这一发现很重要，即使P1左边和P2右边的数据没有排序，我们也可以根据左边最大值和右边最小值来得到中位数。那么如何才能快速得到一个容器中的最大值和最小值呢？我们先到了大顶堆和小顶堆。

解法6：用大顶堆实现左边的的数据容器，小顶堆实现右边的数据容器。往堆中插入一个数据时间复杂度为O(logn)，而得到最大值（或最小值）只需O(1)时间。有一点需要注意，我们要保证数据被平均分配到两个堆中（想想为什么?），因此两堆大小之差不能超过1。实现方法是数据流中奇数位的数插入小顶堆中，偶数位的数插入大顶堆中。同时还要保证大顶堆中的所有数都要小于小顶堆中的数。考虑一种特殊情况，例如，插入偶数位的数，按照分配规则应该插入大顶堆中，但是这个数大于小顶堆的最小值怎么办？如果直接插入大顶堆，就不符合大顶堆所有值都小于小顶堆的值这一条件。可以这样解决：想把该数插入小顶堆，然后进行堆排序，接着讲小顶堆的最小值拿出来插入到大顶堆中，这样就满足所有条件了。同理插入奇数位的数时也要考虑这种特殊情况。

代码实现如下：

class Solution {
public:
	//插入原则：奇数位的数插入小顶堆，偶数位数的插入大顶堆，除特殊情况外
	void Insert(int num)
	{
		/*特殊情况1：当插入奇数位的数num时，应插入小顶堆里，但是当num小于大顶堆的最大值时，
		应将其插入大顶堆，然后将大顶堆的最大值插入小顶堆中*/
		if (((min.size() + max.size()) & 1) == 0)                   
		{
			if (max.size() > 0 && num < max[0])
			{
				max.push_back(num);
				push_heap(max.begin(), max.end());              //进行堆排序
				num = max[0];                                   //找到最大值
				pop_heap(max.begin(), max.end());               //将最大值移除堆（其实就是将最大值放在数组最后一位）
				max.pop_back();                                 //删除
			}
			min.push_back(num);
			push_heap(min.begin(), min.end(),greater<int>());       //构建小顶堆
		}
		else
		{
			/*特殊情况2：当插入偶数位的数num时，应插入大顶堆里，但是当num大于小顶堆的最小值时，
			应将其插入小顶堆，然后将小顶堆的最小值插入大顶堆中*/
			if (min.size() > 0 && num > min[0])
			{
				min.push_back(num);
				push_heap(min.begin(), min.end(),greater<int>());             //进行排序
				num = min[0];                                                 //找到最小值
				pop_heap(min.begin(), min.end(),greater<int>());              //将最小值移除堆（同上）
				min.pop_back();                                               //删除
			}
			max.push_back(num);
			push_heap(max.begin(), max.end());
		}
	}

	double GetMedian()
	{
		int size = min.size() + max.size();
		if (size == 0)
			return 0;
		if ((size & 1) == 1)
			return min[0];
		else
			return (double)(max[0] + min[0]) / 2;
	}

private:
	vector<int> min;                 //用来模拟小顶堆
	vector<int> max;                 //用来模拟大顶堆
};

关于heap算法可参考：http://blog.csdn.net/yf_li123/article/details/70242850