Золотая середина. Поиск медианного элемента потока входных чисел

[middle]

Можно просто собрать в массив и отсортировать его. Получаем те же O(n) по памяти и те же O(n*log n) по времени. При этом сортировка некоторыми алгоритмами будет в невырожденном случае опережать сортировку кучей, которую вы фактически предложили, за счёт меньшей константы (которая тоже имеет значение).

А потом идём в гугл и таки находим алгоритм с линейным средним временем выполнения…

[ilyaglar]

А разве не достаточно хранить медиану и два числа слева/справа от неё, плюс наверное метку чёт/нечет. А так куча это интересно, но тут излишне, кажется?

[zetyquickly]

Привет. Нужно посчитать сложность такого подхода, насколько он будет сопоставим.

Без формальных выкладок приведу пример, который, на мой взгляд, обоснует применение кучи.

Каждый новый элемент может быть вставлен либо во множество "большие медианы", либо "меньшие медианы". пусть он больше медианы, тогда нам повезёт, если он между элементами тройки <"слева", "медиана", "справа">, в этом случае мы сможем запросто обновить тройку. Но если он окажется далеко справа, то нужно быстро добыть из правого множества наименьший элемент. Для этого кучу здесь используем.

Надеюсь, пример на пальцах понятен :)

[zetyquickly]

Привет. В целом, кажется реально реализовать поддержание массива отсортированным, вставляя за O(logN) очередной элемент на место, найденное бинарным поиском, затем выдавать центральный элемент массива по запросу.

[middle]

Привет!

Место вставки можно найти за O(log N), но сама вставка занимает O(N).

[zetyquickly]

И правда, а я под другими комментариями с похожей идеей тоже говорю, что O(N logN) получится :) Спасибо!

[wslc]

Задача не очень удачно сформулирована: лучше было сказать, что после каждого нового элемента мы хотим знать медиану. Тогда понятно, зачем хипы, а не просто сортировка/quick-select

[zetyquickly]

Да, именно так в онлайне. Хорошо задачу описали в этом комментарии, в статье я пытался это менее формальным языком описать. Эффект простоты описания не был достигнут :)

[malkovsky]

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

В С++ к слову нахождение порядковой статистики за линейное время есть в стандарте

Полагаю, что постановка задачи все-таки следующая: требуется реализовать структуру данных, которая поддерживает два запроса

• Добавить элемент в множество
• Найти текущую медиану

Тут уже быстрая сортировка не даст нужного эффекта. Стоит отметить, что log(n) для обоих операций можно добиться обычным бинарным деревом поиска без особых ухищрений c кучами. В любом случае говорить о том, что быстрее log(n) не получить довольно наивно, хоть я и не знаю, существует ли кучи, которые умеют одновременно удалять и добавлять за O(1). В целом кажется, что есть возможности исхитриться и делать меньше удалений.

[zetyquickly]

Да, постановка задачи именно такая. В онлайне добавлять элемент и уметь доставать медиану.

[GarryC]

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

[zetyquickly]

Часто медиана не равна среднему. Плюс, среднее в онлайне поддерживать тоже можно с некоторой точностью, точно посчитать, нужно каждый шаг складывать все N элементов

[zetyquickly]

Ваше решение мне также кажется валидным. Но скорее всего, итоговая сложность также будет O(NlogN), поскольку нужно искать место, куда воткнуть очередной элемент N раз. Столько раз, сколько в онлайне нам предоставили новое число

UPD: дали хороший комментарий, что вставка занимает O(N) (в вашем комменте это также говорится). Поэтому решение с поиском за O(logN) и вставку, осуществляемую N раз, по итогу даст квадратичную сложность. А не как я выше написал