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

Question

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

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

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 类的函数调用。

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() 函数。