Структура для удаления половины наибольших элементов

[BanmaN]

Здравствуйте.

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


Понятно, что если 2-ую операцию реализовать за время $O(n)$, то условие будет выполнено.
Даже ясна одна из реализаций: нужно удалить - считаешь медиану (такой элемент, что в упорядоченном множестве находился бы посередине(или один из элементов, если их несколько) множества и разбиваешь на 2 половинки: больше её и меньше, большую удаляешь. Для нахождения медианы есть детерминированный алгоритм, работающий за $O(n)$, а для второго достачно и вовсе одного пробега по массиву. Т.е. условие выполнено.
Но проблема в том, что для нахождения медианы хоть и требуется линейное время, но коэффицент очень велик, поэтому поступать так не очень хорошо, и, скорее всего, есть другое решение. Подскажите, пожалуйста.

Спасибо.

p.s. задача из книги Кормен "Алгоритмы, построение и анализ".

[Dmitriy_M]

список?

[BanmaN]

Как вы там удалите $\frac{n}{2}$ наибольших элементов за $O(n)$?
Удалите-то точно за $O(n)$, но наибольших ли.

Может я чего-то не понял. Поясните поподробней, пожалуйста.

[Dmitriy_M]

Возьму двусвязный список. Буду поддерживать инвариант, что список упорядоченный. Вставка в список $O(n)$, максимальный элемент всегда в конце, поэтому удаление происходит за $O(1)$.

[venco]

BanmaN в сообщении #469465 писал(а):

Здравствуйте.

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


Понятно, что если 2-ую операцию реализовать за время $O(n)$, то условие будет выполнено.
Даже ясна одна из реализаций: нужно удалить - считаешь медиану (такой элемент, что в упорядоченном множестве находился бы посередине(или один из элементов, если их несколько) множества и разбиваешь на 2 половинки: больше её и меньше, большую удаляешь. Для нахождения медианы есть детерминированный алгоритм, работающий за $O(n)$, а для второго достачно и вовсе одного пробега по массиву. Т.е. условие выполнено.
Но проблема в том, что для нахождения медианы хоть и требуется линейное время, но коэффицент очень велик, поэтому поступать так не очень хорошо, и, скорее всего, есть другое решение. Подскажите, пожалуйста.

Спасибо.

p.s. задача из книги Кормен "Алгоритмы, построение и анализ".

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

[BanmaN]

Так да, только медиану я даже не представляю как поддерживать. Единственная идея - использовать две очереди с приоритетами (одну-возрастающую, другую - убывающую) и отдельно один элемент(медиану), но тогда вставка займёт $O(lg n)$.

Про коэффициент я к тому что такая реализация не пойдёт=).

Dmitriy_M, читайте внимательно главный пост. Там всё написано. Верхняя граница для вставки - $O(1)$.

[Dmitriy_M]

[quote="BanmaN в [url=http://dxdy.ru/post469676.html#p469676] Верхняя граница для вставки - $O(1)$.[/quote]
Вряд ли такая структура данных существует.

[BanmaN]

Я нашёл сайт с решением и там написано то же самое, что и я сказал=)
Видимо, лучшего решения, значит, не найти...

Пруфлинк: http://courses.csail.mit.edu/6.046/fall01/handouts/ps7sol.pdf.