中位数维护的实施

Question

我正在尝试解决一个在线课程中的问题，我相信我被卡住了。

这就是问题所在

该问题的目标是实现“中值维护”算法。文本文件包含按未排序顺序从1到10000的整数列表；您应该将其视为一个数字流，一个接一个地到达。让xi表示文件的第i个数字，第k个中值mk被定义为数字x1，…，xk的中值。（因此，如果k是奇数，那么mk是x1，…，xk中的第（（k1）/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），另一个用于存储小于中值的元素。对于每个新元素，如果其小于（或等于）最大堆中的最大元素，我将其添加到＜code＞max_heap_elements＜/code＞中。我

如果新元素大于最小堆的最小元素，我将其添加到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

我也经历了同样的过程，所以我的解决方案就在这里。

import heapq
import statistics

with open('home_work_week3_Median.txt', 'r') as file:
    line = file.read().strip().split('\n')
file.close()
assert len(line) == 10000

# solution with heapq
nn = []
num = 0

for n, v in enumerate(line):

    nn.append(v) 

#     index = (len(nn) - 1) // 2 # here we get the index of new list
#     new = heapq.nsmallest(n+1, nn) # get the smallest num of heapqed list
#     print(new[index], new, index)

    # here we combine it into one line
    num += int(heapq.nsmallest(n+1, nn)[(len(nn) - 1) // 2])

num%10000


# solution with statistics lib
num = 0

for index, number in enumerate(test):
    num += int(statistics.median_low(test[:index+1]))

num%10000

我不知道我的解决方案是否正确，两种解决方案的执行时间相同（约11秒）。我相信会更好

Answer 2

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

相反你应该做

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）解决方案，但是，通过重复调用堆，max和min等函数，您将无法获得所需的时间复杂性。

取代< code > min(min _ heap _ elements) write < code > min _ heap _ elements[0]，移除< code>heappush之后的< code>heapify调用，取代list的< code > pop use < code > heap pop 。

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

编辑:如果时间复杂度不是一个要求，您可以只使用标准库中的函数< code > statistics . median _ low 。