Поиск подходящей структуры данных

Question

У меня есть N ключей.

Мне нужно найти структуру данных, которую я могу сделать с помощью следующих операций:

1. построение в O (N)

2. нахождение мин в O (1)

3. удаление медианы в O (logn)

4. найти n / 2 + 7-е наибольшее число

Я думал об использовании минимальной кучи (сборка O (n), минимальная O (1) - root).

Однако мне трудно найти способ сделать 3 и 4.

Я думаю, что медиана должна быть на листьях, но это насколько я достиг.

Answer 1

Популярный вопрос, заданный в Data Structures 1 Exams / HWS / Tutorials. Я постараюсь дать вам несколько советов, если их недостаточно, прокомментируйте, и я дам вам больше подсказок.

1. Помните, что вам не нужно использовать только одну структуру данных, вы можете использовать несколько структур данных.
2. Напомним определение медианы: n / 2 чисел больше, а n / 2 чисел меньше
3. Какие структуры данных, как вы знаете, встроены в O (n), а сложные операции над ними - O (logn) или меньше? - Перечитайте учебные слайды по этим структурам данных.
4. Возможно, вам будет проще решить 1 + 3 отдельно от 1 + 2, а затем подумать о слиянии.

Answer 2

Когда вы говорите, что построение в O (n), вы имеете в виду, что сложение должно быть O (n), или что вы должны построить набор элементов в O (n), чтобы сложение было O (1 )

Вы можете дополнить практически любую структуру данных дополнительной ссылкой для извлечения минимального элемента за постоянное время.

Для # 3 кажется, что вам нужно найти медиану в O (lg n) и удалить в O (1), или наоборот.

Для # 4 вы не указали временную сложность.

Для других плакатов - это помечено как домашнее задание. Пожалуйста, дайте подсказки, а не размещайте ответ.

Answer 3

Простой отсортированный массив решит проблему для № 2, № 3 и № 4. Но для его построения потребовалось бы O (n n ). Тем не менее, нет никаких ограничений на сложность пространства. Я много думаю о том, чтобы использовать концепцию хеширования при построении структуры данных, которая снизила бы порядок до O (n).

Надеюсь, это поможет. Вернусь, если найду лучшее решение