Comments 14
А потом идём в гугл и таки находим алгоритм с линейным средним временем выполнения…
А разве не достаточно хранить медиану и два числа слева/справа от неё, плюс наверное метку чёт/нечет. А так куча это интересно, но тут излишне, кажется?
Привет. Нужно посчитать сложность такого подхода, насколько он будет сопоставим.
Без формальных выкладок приведу пример, который, на мой взгляд, обоснует применение кучи.
Каждый новый элемент может быть вставлен либо во множество "большие медианы", либо "меньшие медианы". пусть он больше медианы, тогда нам повезёт, если он между элементами тройки <"слева", "медиана", "справа">, в этом случае мы сможем запросто обновить тройку. Но если он окажется далеко справа, то нужно быстро добыть из правого множества наименьший элемент. Для этого кучу здесь используем.
Надеюсь, пример на пальцах понятен :)
Привет. В целом, кажется реально реализовать поддержание массива отсортированным, вставляя за O(logN) очередной элемент на место, найденное бинарным поиском, затем выдавать центральный элемент массива по запросу.
Задача не очень удачно сформулирована: лучше было сказать, что после каждого нового элемента мы хотим знать медиану. Тогда понятно, зачем хипы, а не просто сортировка/quick-select
Да, именно так в онлайне. Хорошо задачу описали в этом комментарии, в статье я пытался это менее формальным языком описать. Эффект простоты описания не был достигнут :)
В С++ к слову нахождение порядковой статистики за линейное время есть в стандарте
Полагаю, что постановка задачи все-таки следующая: требуется реализовать структуру данных, которая поддерживает два запроса
- Добавить элемент в множество
- Найти текущую медиану
Тут уже быстрая сортировка не даст нужного эффекта. Стоит отметить, что log(n) для обоих операций можно добиться обычным бинарным деревом поиска без особых ухищрений c кучами. В любом случае говорить о том, что быстрее log(n) не получить довольно наивно, хоть я и не знаю, существует ли кучи, которые умеют одновременно удалять и добавлять за O(1). В целом кажется, что есть возможности исхитриться и делать меньше удалений.
Если предположить, что медиана наименее отклоняется от среднего, то решение будет O(n), но предположение сильное и требует доказательства.
Ваше решение мне также кажется валидным. Но скорее всего, итоговая сложность также будет O(NlogN), поскольку нужно искать место, куда воткнуть очередной элемент N раз. Столько раз, сколько в онлайне нам предоставили новое число
UPD: дали хороший комментарий, что вставка занимает O(N) (в вашем комменте это также говорится). Поэтому решение с поиском за O(logN) и вставку, осуществляемую N раз, по итогу даст квадратичную сложность. А не как я выше написал
Золотая середина. Поиск медианного элемента потока входных чисел