Отслеживание медианы расширяющегося массива

Вопрос на интервью:

Отредактировано ниже Вам дан массив. Вы делаете из него 2 кучи: одну минимальную, а другую - максимальную. Теперь найдите медианное значение массива, используя эти 2 предоставленные кучи, за время O (nlog n).

Исправленный вопрос Числа генерируются случайным образом и сохраняются в (расширяющемся) массиве. Как бы вы отслеживали медианное значение?

Решение Эту проблему можно решить, используя 2 кучи, а доступ к медиане всегда можно получить за время O (1).