Python：使用MaxHeap和MinHeap查找运行中值

Question

我试图返回一系列流媒体数据的运行中值。为此，我使用max heap（将值存储在序列的下半部分）和min heap（将值存储在序列的上半部分）。在

特别是，我使用的是来自heapq模块（https://docs.python.org/2/library/heapq.html）的Python（2.0）内置最小堆数据结构。为了构建最大堆，我只需使用需要放入堆中的数字的负数。在

我的Python代码如下：

import heapq

maxh = []
minh = []
vals=[1,2,3,4,5,6,7,8,9,10]
for val in vals:

    # Initialize the data-structure and insert/push the 1st streaming value
    if not maxh and not minh:
        heapq.heappush(maxh,-val)
        print float(val)
    elif maxh:

        # Insert/push the other streaming values
        if val>-maxh[0]:
            heapq.heappush(minh,val)
        elif val<-maxh[0]:
            heapq.heappush(maxh,-val)

        # Calculate the median
        if len(maxh)==len(minh):
            print float(-maxh[0]+minh[0])/2
        elif len(maxh)==len(minh)+1:
            print float(-maxh[0])
        elif len(minh)==len(maxh)+1:
            print float(minh[0])

        # If min-heap and max-heap grow unbalanced we rebalance them by
        # removing/popping one element from a heap and inserting/pushing
        # it into the other heap, then we calculate the median
        elif len(minh)==len(maxh)+2:
            heapq.heappush(maxh,-heapq.heappop(minh))
            print float(-maxh[0]+minh[0])/2
        elif len(maxh)==len(minh)+2:
            heapq.heappush(minh,-heapq.heappop(maxh))
            print float(-maxh[0]+minh[0])/2

下面是我为检查代码而构建的测试用例的完整列表：

^{pr2}$

我的代码对我来说还可以，但是我不能用在线法官（https://www.hackerrank.com/challenges/ctci-find-the-running-median/problem）传递10个测试用例中的4个。在

你有什么提示吗？在

Answer 1

问题在于：

    # Insert/push the other streaming values
    if val>-maxh[0]:
        heapq.heappush(minh,val)
    elif val<-maxh[0]:
        heapq.heappush(maxh,-val)

如果val == maxh[0]，则该项永远不会推送到两个堆中。您应该能够通过测试用例[1,1,2]揭示错误。在

一个简单的解决方法是：

^{pr2}$