Хорошо, с обновлением вопроса, так что цель ясна (не просто найти медиану, но заново находить медиану каждый раз, когда вы получаете новое число), я думаю, что есть способ.
Я бы начал с пары куч: максимальная куча и минимальная куча. Мин-куча будет содержать числа больше, чем медиана, а максимальная куча - числа меньше медианы. Когда вы получаете первый номер, это ваша медиана. Когда вы получаете второе, вы вставляете меньшее из двух в максимальную кучу, а большее из двух в минимальную кучу. Медиана - это среднее из наименьшего значения в минимальной куче и наибольшее в максимальной куче.
Наряду с двумя кучами вам потребуется хранилище для единственного целого числа, которое будет текущей медианой, когда вы получили нечетное количество входных данных. Вы заполняете это довольно просто: если вы получаете ввод с полным списком, вы в основном сортируете эти два элемента (новый номер и старое медиану) и вставляете меньшее в кучу для меньших элементов и большее в кучу для более крупных предметов. Тогда ваша новая медиана будет средним основанием этих двух куч (и вы пометите другое хранилище как пустое).
Когда вы получите новый номер с этим пустым, вы сравните новый номер с медианой. Если это между числами в качестве основы кучи, это новая медиана, и все готово. В противном случае, извлеките число из базы, которое должно содержать медиану (большие числа, если новое число больше, меньше, если оно меньше), и поместите его в срединную точку, затем вставьте новое число в кучу, которая пришла.
По крайней мере, если память служит, извлечение / вставка в кучу должно быть O (log N). Я считаю, что все остальное должно быть постоянной сложности.