python - 实现中值维护

Question

我正在尝试解决我正在学习的在线类(class)中的问题，但我相信我陷入了困境。

这就是问题

The goal of this problem is to implement the "Median Maintenance" algorithm. The text file contains a list of the integers from 1 to 10000 in unsorted order; you should treat this as a stream of numbers, arriving one by one. Letting xi denote the ith number of the file, the kth median mk is defined as the median of the numbers x1,…,xk. (So, if k is odd, then mk is ((k+1)/2)th smallest number among x1,…,xk; if k is even, then mk is the (k/2)th smallest number among x1,…,xk.)

Find the sum of the 1000 medians.

下面是我的代码，它输出了错误的答案，我似乎无法弄清楚出了什么问题

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_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]

Answer 1

问题在于如何计算两个堆的中位数，因为当索引为奇数时，不能保证左侧堆比右侧堆多一个元素。

相反，你应该这样做

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]，而是删除 heappush 之后的 heapify 调用，使用 heappop 而不是列表的 pop。

最后，对于最大堆，您可以有一个包含负值的列表，因为 heapq 模块不支持最大堆，它们仅“支持”一些操作，例如 _heappop_max >，但没有 _heappush_max，因此您始终需要调用 _heapify_max。

编辑: 如果时间复杂度不是要求，您可以使用标准库中的函数statistics.median_low。