C++ Эффективный расчет бегущей медианы [дубликат]
На этот вопрос уже есть ответ здесь:
Те из вас, кто читал мои предыдущие вопросы, знают о моей работе в понимании и реализации быстрой сортировки и быстрого выбора, а также некоторых других базовых алгоритмов.
Быстрый выбор используется для вычисления k-го наименьшего элемента в несортированном списке, и эту концепцию также можно использовать для поиска медианы в несортированном списке.
На этот раз мне нужна помощь в разработке эффективного метода для вычисления бегущей медианы, потому что quickselect не лучший выбор, так как он должен пересчитывать каждый раз, когда список изменяется. Поскольку quickselect должен перезапускаться каждый раз, он не может использовать преимущества предыдущих вычислений, поэтому я ищу другой алгоритм, который похож (возможно), но более эффективен в области бегущих медиан.