Да, именно так в онлайне. Хорошо задачу описали в этом комментарии, в статье я пытался это менее формальным языком описать. Эффект простоты описания не был достигнут :)
Привет. В целом, кажется реально реализовать поддержание массива отсортированным, вставляя за O(logN) очередной элемент на место, найденное бинарным поиском, затем выдавать центральный элемент массива по запросу.
Привет. Нужно посчитать сложность такого подхода, насколько он будет сопоставим.
Без формальных выкладок приведу пример, который, на мой взгляд, обоснует применение кучи.
Каждый новый элемент может быть вставлен либо во множество "большие медианы", либо "меньшие медианы". пусть он больше медианы, тогда нам повезёт, если он между элементами тройки <"слева", "медиана", "справа">, в этом случае мы сможем запросто обновить тройку. Но если он окажется далеко справа, то нужно быстро добыть из правого множества наименьший элемент. Для этого кучу здесь используем.
Да, именно так в онлайне. Хорошо задачу описали в этом комментарии, в статье я пытался это менее формальным языком описать. Эффект простоты описания не был достигнут :)
Привет. В целом, кажется реально реализовать поддержание массива отсортированным, вставляя за O(logN) очередной элемент на место, найденное бинарным поиском, затем выдавать центральный элемент массива по запросу.
Привет. Нужно посчитать сложность такого подхода, насколько он будет сопоставим.
Без формальных выкладок приведу пример, который, на мой взгляд, обоснует применение кучи.
Каждый новый элемент может быть вставлен либо во множество "большие медианы", либо "меньшие медианы". пусть он больше медианы, тогда нам повезёт, если он между элементами тройки <"слева", "медиана", "справа">, в этом случае мы сможем запросто обновить тройку. Но если он окажется далеко справа, то нужно быстро добыть из правого множества наименьший элемент. Для этого кучу здесь используем.
Надеюсь, пример на пальцах понятен :)
Согласен, очень интересный вопрос, насколько похожи математические нейронные сети, созданные человеком, и сети в головах животных