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

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

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

объединение данных на основе скользящего временного окна в R

Моя идея:

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

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

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

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

Любая помощь очень ценится.

Спасибо