найти медиану в движущемся окне фиксированного размера вдоль длинной последовательности данных

Учитывая последовательность данных (она может иметь дубликаты), движущийся фиксированный размер окно, перемещайте окно на каждой итерации от начала данных последовательность, такая, что (1) самый старый элемент данных удаляется из окна, а новые данные элемент помещается в окно (2) найти медиану данных внутри окна при каждом перемещении.

Следующие сообщения бесполезны.

Эффективно находить медианное значение случайной последовательности

соединяя данные на основе движущегося временного окна в R

Моя идея:

Используйте 2 кучи для хранения медианы. В боковой части окна отсортируйте данные в окне в первой итерации минимальная куча содержит большую часть, а максимальная куча держит меньшую часть. Если в окне нечетное количество данных, максимальная куча возвращает медиану, в противном случае среднее арифметическое верхних элементов две кучи - это медиана.

Когда в окно вводятся новые данные, удаляйте самые старые данные из одного окна. кучи и сравните новые данные с вершиной максимальной и минимальной кучи, чтобы что бы решить в какую кучу данные класть. Затем найдите медиану просто как в первой итерации.

Но как найти элемент данных в куче — проблема. Куча — это двоичный файл дерево не является бинарным деревом поиска.

Можно ли решить ее за O(n) или O(n * lg m), где m — размер окна, а пробел: O(1) ?

Будем признательны за любую помощь.

Спасибо