给定一个数据流，找出中位数，由于数据流中的数据并不是有序的，所以我们首先应该想个方法让其有序。如果我们用vector来保存数据流的话，每进来一个新数据都要给数组排序，很不高效。所以之后想到用multiset这个数据结构，是有序保存数据的，但是它不能用下标直接访问元素，找中位数也不高效。这里用到的解法十分巧妙，我们使用大小堆来解决问题，其中小堆保存右半段较大的数字，大堆保存左半段较小的数组。这样整个数组就被中间分为两段了。当大堆和小堆中的数字一样多时，我们取出大堆小堆的首元素求平均值，当大堆元素多时，取大堆首元素为中位数，参见代码如下：
class MedianFinder { public: /** initialize your data structure here. */ MedianFinder() { } void addNum(int num) { bigQ.push(num); smallQ.push(bigQ.top()); bigQ.pop(); if(bigQ.size()<smallQ.size()){ bigQ.push(smallQ.top()); smallQ.pop(); } } double findMedian() { return bigQ.size()>smallQ.size()?bigQ.top():0.5*(bigQ.top()+smallQ.top()); } private: # 最小堆数据从小到大存储，放数组右边元素 priority_queue<int, vector<int>, less<int>> smallQ; # 最大堆数据从大到小存储，放数组左边元素 priority_queue<int, vector<int>, greater<int>> bigQ; }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */
原文：https://www.cnblogs.com/a-little-v/p/10482129.html