Структура данных, поддерживающая быструю вставку и вычисление медианы
Мне нужна структура данных, которая поддерживает следующие операции:
- Вставить число;
- Найти медиану всех вставленных чисел;
- (дополнительно) Найти заранее известный квантиль (0-1) всех вставленных чисел;
Самый простой способ - сортировка чисел после каждой вставки, но это не быстро. Есть ли более быстрое решение?
Ответы (2 шт):
Автор решения: Igor
→ Ссылка
Что такое "быстро" - каждый понимал по-своему. A.Гайдар "Чук и Гек"
Вставляйте сразу на нужное место, тогда сортировать ничего не придется. Вставка в сортированный список - O(logN).
Автор решения: becouse
→ Ссылка
Самый быстрый вариант в смысле поиска и добавления это бинарное поисковое дерево.
- Вставка O(logN)
- поиск медианы O(logN)
- поиск квантиля (выводится из медианы) O(logN)
Создание бинарного дерева на Java
Поиск медианы в бинарном дереве.