Наличие определенной структуры данных
Мне интересно, может ли существовать такая структура данных при следующих критериях и временах (может быть сложно)?
если мы получим несортированный список L, мы построим из него структуру данных следующим образом:
- Build (L, X) - за время O (n) мы строим структуру S из несортированного списка из n элементов.
- Insert (y, S) под O (lg n) мы вставляем z в структуру S
- DEL-MIN (S) - под O (lg n) мы удаляем минимальный элемент из S
- DEL-MAX (S) - под O (lg n) удаляем максимальный элемент из S
- DEL-MId (S) - под O (lg n) удаляем верхний медиальный (потолочная функция) элемент из S
проблема в том, что список L не отсортирован. может ли существовать такая структура данных?
список содержит числа в несортированном виде. если это был связанный список, возможно ли это? Я знаю, что это сложно, поэтому я не понимаю, может ли оно существовать
Конечно нет. Вы не можете помещать элементы в структуру данных без обработки элементов. Ваш вопрос похож на "Я хочу сделать миллион вещей, могу ли я сделать миллион вещей, сделав менее миллиона вещей?"
@JohnColeman, давайте делать это медленно, от случая к случаю. как лучше всего реализовать Build (L, X) (под O (n)) и Insert (y, S) (под O (log n))?
Я надеюсь, что «под O (.)» Означает «в O (.)». В соответствии с этой предпосылкой сбалансированное двоичное дерево поиска, которое сохраняет размеры поддеревьев, является именно такой структурой данных. Фактически, с некоторыми популярными языками это возможно только с начальным усилием понимания: например, можно построить такое дерево из это расширение GCC стандартной библиотеки C++.
@Gassa, вы не можете построить сбалансированное двоичное дерево поиска за O (n) время.
@PaulHankin Хм, я могу, но только тогда, когда элементы уже отсортированы, иначе это была бы сортировка на основе сравнения за O (n). Для несортированных данных это O (n log n). Спасибо за улов! Кучи - это то, что вам нужно, как в вашем ответе.
Ответы 1
DEL-MIN и DEL-MAX просты: сохраняйте min-heap и max-heap всех элементов. Единственный трюк заключается в том, что вы должны хранить индексы значения в куче, чтобы, когда (например) вы удаляете максимум, вы также можете найти его и удалить в минимальной куче.
Для DEL-MED вы можете сохранить максимальную кучу элементов меньше медианы и минимальную кучу элементов, большую или равную медиане. Полное описание находится в этом ответе: Структура данных для поиска медианы. Обратите внимание, что в этом ответе возвращается медиана пола, но это легко исправить. Опять же, вам нужно использовать уловку перекрестной индексации, чтобы ссылаться на другие структуры данных, как в первой части. Вам также нужно будет подумать, как это обрабатывает повторяющиеся элементы, если это возможно в вашей постановке проблемы. (При необходимости вы можете сделать это, сохраняя повторяющиеся элементы как (count, value) в вашей куче, но это немного усложняет перебалансировку кучи при вставке / удалении).
Можно ли все это построить за O (n)? Да - вы можете найти медианное значение n вещей за время O (n) (используя алгоритм медианы медианы), а кучи можно построить за время O (n).
Таким образом, структура данных состоит из 4 кучи (минимальная куча всех элементов, максимальная куча всех элементов, максимальная куча пола (n / 2) наименьших элементов, минимальная куча ceil ( n / 2) наибольшие элементы, все с перекрестными индексами друг к другу.
Вам не нужны отдельные min-heap и max-heap для DEL-MIN и DEL-MAX. Есть min-max куча.
Как вы могли строить структуру данных в сублинейное время? Какими свойствами, по вашему мнению, обладает этот список? Это связанный список? Что-то другое?