Осуществление медианного обслуживания

Question

Я пытаюсь решить проблему с помощью онлайн-курса, который я посещаю, и я считаю, что застрял.

Это проблема

Цель этой проблемы - реализовать алгоритм «Медианное обслуживание». Текстовый файл содержит список целых чисел от 1 до 10000 в несортированном порядке;Вы должны рассматривать это как поток чисел, прибывающих один за другим. Если xi обозначает i-й номер файла, то k-я медиана mk определяется как медиана чисел x1,…, xk. (Таким образом, если k нечетно, то mk является ((k + 1) / 2) наименьшим числом среди x1,…, xk; если k четное, то mk является (k / 2) -ым наименьшим числом среди x1,…, Xk.)

Найдите сумму 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_heap_elements. i

Если новый элемент больше минимального элемента кучи min, я добавляю его к 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], удалите вызов heapify после heappush, вместо pop списка используйте heappop.

Наконец, для максимальной кучи можно получить список с отрицательными значениями, поскольку модуль heapq не поддерживает максимальные кучи, они только «поддерживают» некоторые операции, такие как _heappop_max, но _heappush_max нет,поэтому вам всегда нужно будет вызывать _heapify_max.

EDIT: , если сложность времени не требуется, вы можете просто использовать функцию statistics.median_low из стандартной библиотеки.