Алгоритм Вопрос по поиску медианы nos

Question

При заданной последовательности триллионов действительных чисел на диске ...

Как бы вы вычислили работающий MEDIAN для каждой тысячи записей, т.е.медиана a [0], ...., a [999],

второй точкой будет медиана a [1], ..., a [1000],

третья точка была бы медианой [2], ..., [1001] и т. д.?

Answer 1

Наивное решение на самом деле не так уж и плохо, сохраняйте отсортированный список из 1000 чисел в памяти и каждый раз, когда вы переходите к следующему индексу, удаляйте a[i-1] из отсортированного списка и добавляйте a[i+999] в отсортированный список.

Если у вас есть это, легко вычислить медиану в отсортированном списке.

Вопрос в том, как вы справляетесь лучше?

Answer 2

Подсказка: сохраняйте максимальную кучу, в которой хранятся наименьшие 500 из 1000 чисел, и поддерживайте минимальную кучу, в которой хранятся самые большие 500.