了解使用堆从整数流中获取平均值

Question

我正在关注以下博客并了解如何以非常微妙的方式获得中位数。博客是here

现在，我将以下函数添加到 streamMedian class 以获取插入数字的平均值，但未获得所需的输出

import heapq

class streamMedian:
    def __init__(self):
        self.minHeap, self.maxHeap = [], []
        self.N=0


    def insert(self, num):
        if self.N%2==0:
            heapq.heappush(self.maxHeap, -1*num)
            self.N+=1
            if len(self.minHeap)==0:
                return
            if -1*self.maxHeap[0]>self.minHeap[0]:
                toMin=-1*heapq.heappop(self.maxHeap)
                toMax=heapq.heappop(self.minHeap)
                heapq.heappush(self.maxHeap, -1*toMax)
                heapq.heappush(self.minHeap, toMin)
        else:
            toMin=-1*heapq.heappushpop(self.maxHeap, -1*num)
            heapq.heappush(self.minHeap, toMin)
            self.N+=1

    def getMedian(self):
        if self.N%2==0:
            return (-1*self.maxHeap[0]+self.minHeap[0])/2.0
        else:
            return -1*self.maxHeap[0]

    def getMean(self):
        sum = 0
        for num in self.maxHeap:
            sum += num
        for num in self.minHeap:
            sum += num 
        return sum/self.N

这是对 streamMedian 的函数调用 class。

test = streamMedian()
test.insert(1)
test.insert(2)
test.insert(3)
print test.getMedian()
print test.getMean()

此处的中位数应为 2，均值应为 2（而不是输出 0）。提前致谢。

Answer 1

您正在向 maxHeap (-1*num) 推送负数。您需要在 getMean() 中反转它，例如：

def getMean(self):
    total = 0
    for num in self.maxHeap:
        total -= num
    for num in self.minHeap:
        total += num 
    return total/self.N

或者：

def getMean(self):
    return (abs(sum(self.maxHeap)) + sum(self.minHeap))/self.N

注意：不要将 sum 用作变量，它会隐藏 python 内置 sum() 函数。

Answer 2

AChampion 的回答正确地识别了您当前代码的问题并提供了合理的修复，同时仍然使用您当前的算法。但是，该算法效率不高（需要 O(N) 时间），您可以做得更好。

具体来说，除了将其推入其中一个堆之外，您还应该将要插入的值添加到累积总和中。这样，当你需要得到一个平均值时，你可以在常数时间内计算它（只需要一个除法）：

class streamMedian:
    def __init__(self):
        self.minHeap, self.maxHeap = [], []
        self.cumulative_sum = 0.0             # new instance variable
        self.N=0


    def insert(self, num):
        self.cumulative_sum += num            # add each value to it
        # rest of insert code...

    # median code...

    def getMean(self):
        return self.cumulative_sum / self.N   # compute the mean in constant time

请注意，如果您使用的是 Python 2（看起来是这样），请务必使用浮点值 0.0 而不是整数 [=] 初始化 cumulative_sum 14=]（否则是自然的）。当您将 Python 2 中的两个整数相除时，您将得到另一个整数，向下舍入。如果您要计算 1 和 2 的平均值（您期望 1.5，但如果您得到 1就做 (1 + 2) / 2）。 Python 3 在这方面做得更好（您总是从常规除法中得到一个浮点数，并且可以使用 // 运算符明确请求 "floor" 除法）。如果您想在 Python 2 中获得相同的语义，您可以将 from __future__ import division 放在模块的顶部。

了解使用堆从整数流中获取平均值

Understanding to get mean from integer stream using heap

python

algorithm

heap