如果您不能一次将所有项保存在内存中，这个问题就会变得更加困难。堆解决方案要求您一次将所有元素保存在内存中。这在这个问题的大多数实际应用中是不可能的。

相反，当您看到数字时，请记录您看到每个整数的次数。假设4个字节整数，即2^32个桶，或最多2^33个整数(每个int的key和count)，即2^35字节或32GB。它可能会比这个小得多，因为您不需要存储键或为那些为0的条目计数(例如。就像python中的defaultdict)。插入每个新整数需要常数时间。

然后在任意点，要找到中位数，只需使用计数来确定哪个整数是中间元素。这需要常数时间(虽然是一个很大的常数，但仍然是常数)。

如果您不能一次将所有项保存在内存中，这个问题就会变得更加困难。堆解决方案要求您一次将所有元素保存在内存中。这在这个问题的大多数实际应用中是不可能的。

相反，当您看到数字时，请记录您看到每个整数的次数。假设4个字节整数，即2^32个桶，或最多2^33个整数(每个int的key和count)，即2^35字节或32GB。它可能会比这个小得多，因为您不需要存储键或为那些为0的条目计数(例如。就像python中的defaultdict)。插入每个新整数需要常数时间。

然后在任意点，要找到中位数，只需使用计数来确定哪个整数是中间元素。这需要常数时间(虽然是一个很大的常数，但仍然是常数)。

如果输入的方差是统计分布的(如正态分布、对数正态分布等)，那么从任意长的数据流中估计百分位数/中位数是一种合理的方法。

int n = 0;  // Running count of elements observed so far  
#define SIZE 10000
int reservoir[SIZE];  

while(streamHasData())
{
  int x = readNumberFromStream();

  if (n < SIZE)
  {
       reservoir[n++] = x;
  }         
  else 
  {
      int p = random(++n); // Choose a random number 0 >= p < n
      if (p < SIZE)
      {
           reservoir[p] = x;
      }
  }
}

“水库”则是一个运行的，均匀的(公平的)，所有输入的样本-无论大小。然后找到中位数(或任何百分位数)是一个简单的问题，即对存储库进行排序并轮询感兴趣的点。

由于存储库的大小是固定的，因此排序可以被认为是有效的O(1) -并且该方法运行的时间和内存消耗都是常数。

高效这个词取决于上下文。这个问题的解决方案取决于执行的查询量与插入量的关系。假设你插入N个数字K次直到最后你对中位数感兴趣。基于堆的算法的复杂度是O(N log N + K)。

考虑下面的替代方案。将数字放入一个数组中，对于每个查询，运行线性选择算法(比如使用快速排序枢轴)。现在你有了一个运行时间为O(K N)的算法。

现在如果K足够小(不频繁查询)，后一种算法实际上更有效，反之亦然。

下面是我简单但有效的算法(c++)，用于从整数流中计算运行中值:

#include<algorithm>
#include<fstream>
#include<vector>
#include<list>

using namespace std;

void runningMedian(std::ifstream& ifs, std::ofstream& ofs, const unsigned bufSize) {
    if (bufSize < 1)
        throw exception("Wrong buffer size.");
    bool evenSize = bufSize % 2 == 0 ? true : false;
    list<int> q;
    vector<int> nums;
    int n;
    unsigned count = 0;
    while (ifs.good()) {
        ifs >> n;
        q.push_back(n);
        auto ub = std::upper_bound(nums.begin(), nums.end(), n);
        nums.insert(ub, n);
        count++;
        if (nums.size() >= bufSize) {
            auto it = std::find(nums.begin(), nums.end(), q.front());
            nums.erase(it);
            q.pop_front();
            if (evenSize)
                ofs << count << ": " << (static_cast<double>(nums[nums.size() / 2 - 1] +
                static_cast<double>(nums[nums.size() / 2]))) / 2.0 << '\n';
            else
                ofs << count << ": " << static_cast<double>(nums[nums.size() / 2]);
        }
    }
}

The bufferSize specifies the size of the numbers sequence, on which the running median must be calculated. When reading numbers from the input stream ifs the vector of the size bufferSize is maintained in sorted order. The median is calculated by taking the middle of the sorted vector, if bufferSize is odd, or the sum of the two middle elements divided by 2, when bufferSize is even. Additinally, I maintain a list of last bufferSize elements read from input. When a new element is added, I put it in the right place in sorted vector and remove from the vector the element added bufferSize steps before (the value of the element retained in the front of the list). In the same time I remove the old element from the list: every new element is placed on the back of the list, every old element is removed from the front. After reaching the bufferSize, both the list and the vector stop to grow, and every insertion of a new element is compensated be deletion of an old element, placed in the list bufferSize steps before. Note, I do not care, whether I remove from the vector exactly the element, placed bufferSize steps before, or just an element that has the same value. For the value of median it does not matter. All calculated median values are output in the output stream.

如果我们想要找到n个最近出现的元素的中值，这个问题有一个精确的解决方案，只需要将n个最近出现的元素保存在内存中。它速度快，规模大。

可索引skiplist支持O(ln n)插入、删除和任意元素的索引搜索，同时保持排序顺序。当再加上一个FIFO队列来跟踪第n个最古老的条目时，解决方案很简单:

class RunningMedian:
    'Fast running median with O(lg n) updates where n is the window size'

    def __init__(self, n, iterable):
        self.it = iter(iterable)
        self.queue = deque(islice(self.it, n))
        self.skiplist = IndexableSkiplist(n)
        for elem in self.queue:
            self.skiplist.insert(elem)

    def __iter__(self):
        queue = self.queue
        skiplist = self.skiplist
        midpoint = len(queue) // 2
        yield skiplist[midpoint]
        for newelem in self.it:
            oldelem = queue.popleft()
            skiplist.remove(oldelem)
            queue.append(newelem)
            skiplist.insert(newelem)
            yield skiplist[midpoint]

以下是完整工作代码的链接(一个易于理解的类版本和一个内联可索引的skiplist代码的优化生成器版本):

http://code.activestate.com/recipes/576930-efficient-running-median-using-an-indexable-skipli/ http://code.activestate.com/recipes/577073。