python - 实现中位数维护

我正在尝试解决一个问题，从网上课程我正在采取，我相信我卡住了。
这就是问题所在
这个问题的目标是实施“中位维修”
算法。文本文件包含从1到
10000个未排序的顺序；您应该将其视为一个数字流，
一个接一个到达让XI表示文件的第i个数，
第k中位数mk被定义为数字x1，…，xk的中位数（因此，如果
k是奇数，那么mk是x1，…，xk中的第（k+1）/2个最小数；如果k
是偶数，那么mk是x1，…，xk中第（k/2）个最小的数。
求出1000个中介的和。
下面是我拥有的代码，它输出的答案是错误的，我似乎不知道出了什么问题

import heapq
# all_ints = list(map(int, open("stanford_algo/course_2_graph_search/median.txt").read().splitlines()))
all_ints = [6331, 2793, 1640, 9290, 225, 625, 6195, 2303, 5685, 1354]
min_heap_elements =  [all_ints[0]] # has all elements more than median
max_heap_elements =  [all_ints[1]] # has all elements less than median
heapq.heapify(min_heap_elements) # has all elements more than median
heapq._heapify_max(max_heap_elements) # has all elements less than median
medians = []
medians.append(all_ints[0])
medians.append(all_ints[1]) #doing this because I can see the first two elements are in decreasing order

for i, next_int in enumerate(all_ints[2:],start=3):
    if next_int > min(min_heap_elements):
        heapq.heappush(min_heap_elements, next_int)
        heapq.heapify(min_heap_elements)
    elif next_int <=  max(max_heap_elements):
        max_heap_elements.append(next_int)
        heapq._heapify_max(max_heap_elements)
    else:
        if len(min_heap_elements) > len(max_heap_elements):
            max_heap_elements.append(next_int)
            heapq._heapify_max(max_heap_elements)
        else:
            heapq.heappush(min_heap_elements, next_int)
            heapq.heapify(min_heap_elements)
    if len(max_heap_elements) - len(min_heap_elements) > 1:
        extract = max_heap_elements.pop(0)
        heapq.heappush(min_heap_elements, extract)
        heapq._heapify_max(max_heap_elements)
        heapq.heapify(min_heap_elements)
    elif len(min_heap_elements) - len(max_heap_elements) > 1:
        extract = min_heap_elements.pop(0)
        max_heap_elements.append(extract)
        heapq._heapify_max(max_heap_elements)
        heapq.heapify(min_heap_elements)
    median = [max(max_heap_elements), min(min_heap_elements)][(i)%2]
    medians.append(median)

sum(medians)%10000 # should be 9335

我用了两堆。一个用于将大于媒体的元素存储在最小堆（min_heap_elements）中，另一个用于存储小于中值的元素（max_heap_elements）对于每个新元素，如果它小于（或等于）max堆的最大元素，我将其添加到max_heap_elements我
如果新元素大于最小堆的最小元素，我将其添加到min_heap_elements。如果这两种情况都没有，我看哪个堆比较短，然后把它加到那个堆上。
然而，我在这里做了一些事情，我不能把我的手指放在上面。
编辑：
这些是我得到的媒介

>>> medians
[6331, 2793, 6331, 2793, 6331, 1640, 2793, 2303, 2793, 2303]

这就是我所期待的

>>> correct_medians
[6331, 2793, 2793, 2793, 2793, 1640, 2793, 2303, 2793, 2303]

最佳答案

问题是如何计算这两个堆的中值，因为当索引为奇数时，左堆不能保证比右堆多出一个元素。
相反你应该这样做

if len(max_heap_elements) == len(min_heap_elements):
    median = max(max_heap_elements)
elif len(max_heap_elements) > len(min_heap_elements):
    median = max(max_heap_elements)
else:
    median = min(min_heap_elements)

另外，注意，如果你正在使用堆，是因为你想要实现一个O(nlogn)解决方案，但是，通过重复调用诸如heapify、max和min之类的函数，你就不会得到期望的时间复杂度。
在min(min_heap_elements)之后删除min_heap_elements[0]调用，而不是list的heapifyuseheappush，而不是popwriteheappop。
最后，对于max heap，您可以有一个带有否定值的列表，因为heapq模块不支持max heap，它们只“支持”一些操作，比如_heappop_max，但是没有_heappush_max，所以您将始终需要调用_heapify_max。
编辑：
如果时间复杂性不是必需的，您可以只从标准库中的函数statistics.median_low。