题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值
首先，题目说一个数据流，就证明可能不能一次读入内存（我们这里用一个数组模拟输入流）
如果将数组从中间一分为二，中间的一个（len是奇数）或者两个元素（len是偶数）左边都比他们小，右边都比他们大，前后两半部分不用排序，只用划分出来就行。那么最后在中间的就是中位数。 左半部分是最大堆，右边是最小堆。
这个想法是使用两个堆（一个最大堆，一个最小堆）保存输入数据。 max_pq是一个大堆，以较小的值保存数据的前半部分，而min_pq是最小堆，以较大的值保存数据的后半个。 每次插入新值时，我们都会先比较它是否小于max_pq的顶部（前一半的最大值），如果是，则将其插入max_pq。 否则，它属于下半部分。 插入后，我们必须平衡前半部分和后半部分，以确保它们具有相同的长度或长度差仅为1,否则最后两个堆顶的元素不在最中间。
priority_queue <int> max_pq; //最大堆，其中最大元素堆顶也小于最小堆中任一元素 priority_queue <int, vector<int>, greater<int> > min_pq; // 最小堆，堆顶最小 bool isAnsValid = false;// 返回0.0时有效与否 void addHeap(int num) { // 插入节点 if (max_pq.empty() || num < max_pq.top()) { // 先插入最大堆 max_pq.push(num); } else { // 当前值比最大堆顶还大，插入最小堆 min_pq.push(num); } if (min_pq.size() > max_pq.size() + 1) { // 最小堆元素个数比最大的超过1，调整 int temp = min_pq.top(); min_pq.pop(); max_pq.push(temp); } else if (max_pq.size() > min_pq.size() + 1) { // 同理 int temp = max_pq.top(); max_pq.pop(); min_pq.push(temp); } } double findCore() { // 找中位数 if (!max_pq.empty()) { isAnsValid = true; // 返回值有效 if (max_pq.size() == min_pq.size()) { // len偶数，取均值 return (max_pq.top() + min_pq.top()) / 2.0; } else { // len奇数，取堆顶 return (max_pq.size() > min_pq.size()) ? max_pq.top() : min_pq.top(); } } else 0.0; // 失败 } double findMidInList(int *nums, int len) { if (nums == NULL || len < 1) return 0.0; while (!max_pq.empty()) max_pq.pop(); // 清空堆 while (!min_pq.empty()) min_pq.pop(); for (int i = 0; i < len; ++i){ // 建堆 addHeap(nums[i]); } return findCore(); }扩展 优先队列（堆） 头文件：#include< queue > 大根堆定义：priority_queue< int >pq 小根堆定义：priority_queue< int ,vector< int >,greater< int > >pq （注意最后两个“>”符号不要连在一起，否则很多编译器误认为是‘>>’运算符）
操作： push() 元素入队 pop() 队首元素出队 top() 取队首元素 empty() 如果队列为空，则返回true（1），否则返回false（0） size() 返回优先队列中拥有的元素个数
