Какая структура данных подходит?

Question

Мне нужна структура данных Java, которая имеет:

• быстрое (O (1)) вставление
• быстрое удаление
• быстрое (O (1))max() function

Какую структуру данных лучше всего использовать?

HashMap почти сработает, но использование java.util.Collections.max() по крайней мере O (n) в размере карты,Вставка и удаление TreeMap слишком медленные.

Есть мысли?

Answer 1

O (1) вставка и O (1) max() являются взаимоисключающими вместе с точкой быстрого удаления.

AO (1) коллекция вставки не будет иметь O (1) max какколлекция не отсортирована.AO (1) max коллекция должна быть отсортирована, таким образом, вставка - O (n).Вам придется прикусить пулю и выбрать между двумя.Однако в обоих случаях удаление должно быть одинаково быстрым.

Если вы можете жить с медленным удалением, у вас может быть переменная, сохраняющая текущий самый высокий элемент, сравните на вставке с этой переменной, max и insert должны быть O(1) тогда.Тогда удаление будет O (n), так как вы должны найти новый самый высокий элемент в тех случаях, когда удаленный элемент был самым высоким.

Answer 2

Если вы можете вставить и удалить O (log n), вы можете получить максимальное значение O (1) с помощью TreeSet или PriorityQueue. O (log n) довольно хорош для большинства приложений.

Answer 3

Если вы согласны с тем, что O (log n) по-прежнему «быстрый», хотя он и не «быстрый (O (1))», то некоторые виды очереди приоритетов на основе кучи выполнят это. См. Таблицу сравнения для различных куч, которые вы можете использовать.

Обратите внимание, что библиотека Java PriorityQueue не очень интересна, она только гарантирует O (n) remove(Object).

Для очередей на основе кучи «удалить» может быть реализовано как «lowerKey», за которым следует «removeMin», при условии, что для этой цели вы зарезервировали значение «отрицательная бесконечность». И так как это максимальный уровень, который вы хотите, инвертируйте все упоминания от «min» до «max» и «уменьшайте» до «увеличивайте» при чтении статьи ...

Answer 4

вы не можете иметь O (1) удаление + вставка + макс
доказательство:
предположим, что вы могли бы, давайте назовем эту базу данных D
с учетом массива A:
1. вставьте все элементы от A до D.
2. создать пустой связанный список L
3. пока D не пусто:
3,1. х
3,2 L.insert_first (x) - O (1)
4. возврат L
здесь мы создали алгоритм сортировки, который является O (n), но это оказалось невозможным! сортировка известна как омега (nlog (n)). противоречие! таким образом, D. не может существовать.

Answer 5

Я очень скептически отношусь к тому, что вставка и удаление журнала (n) TreeMap слишком медленны - время регистрации (n) практически постоянно по сравнению с большинством реальных приложений. Даже если в вашем дереве содержится 1 000 000 000 элементов, если он хорошо сбалансирован, вы будете выполнять только log (2, 1000000000) = ~ 30 сравнений на вставку или удаление, что сравнимо с любой другой хэш-функцией.

Answer 6

Как уже объяснено: для общего случая нет.Однако, если ваш диапазон значений ограничен, вы можете использовать алгоритм сортировки, подобный подсчету, чтобы получить вставку O (1), и, кроме того, связанный список для перемещения указателя max, таким образом, достигая O (1) max и удаления.

Answer 7

Вот вырожденный ответ. Я отметил, что вы не указали, что вы считаете «быстрым» для удаления; если O (n) быстро, то сработает следующее. Создайте класс, который упаковывает HashSet; сохранить ссылку на максимальный элемент при вставке. Это дает две операции с постоянным временем. Для удаления, если удаленный вами элемент является максимальным, вам нужно выполнить итерацию по набору, чтобы найти максимум оставшихся элементов.

Может показаться, что это глупый ответ, но в некоторых практических ситуациях (обобщение) эта идея может действительно быть полезной. Например, вы все равно можете поддерживать самые высокие значения пять в постоянном времени после вставки, и всякий раз, когда вы удаляете элемент, который встречается в этом наборе, вы удаляете его из своего списка из пяти, превращая его в список из четырех и так далее; когда вы добавляете элемент, попадающий в этот диапазон, вы можете расширить его до пяти. Если вы обычно добавляете элементы гораздо чаще, чем удаляете их, то очень редко вам нужно указывать максимум, когда ваш список максимумов пуст, и вы можете восстановить список из пяти самых высоких элементов за линейное время в этот случай.

Answer 8

Такая структура данных была бы потрясающей, и, насколько я знаю, не существует . Другие указали на это.

Но вы можете пойти дальше, если вам все равно, что все это немного сложнее.

Если вы можете «тратить» немного памяти и некоторые усилия на программирование, вы можете одновременно использовать различные структуры данных , объединяя преимущества каждой из них.

Например, мне нужна была отсортированная структура данных, но я хотел иметь O (1) поисков ("это элемент X в коллекции?"), А не O (log n ). Я объединил TreeMap с HashMap (который на самом деле не O (1), но почти , когда он не слишком полный и функция хеширования хороша) и я получил действительно хорошие результаты.

В вашем конкретном случае я бы выбрал динамическую комбинацию между HashMap и пользовательской вспомогательной структурой данных. Я думаю о чем-то очень сложном (хэш-карта + очередь с переменной длиной приоритета), но я приведу простой пример. Просто сохраните все содержимое в HashMap, а затем используйте специальное поле (currentMax), которое содержит только элемент max на карте. Когда вы insert() в вашей объединенной структуре данных, если элемент, который вы собираетесь вставить,> чем текущий max, тогда вы делаете currentMax <- elementGoingToInsert (и вставляете его в HashMap).

Когда вы удаляете элемент из вашей объединенной структуры данных, вы проверяете, равен ли он currentMax, и если он есть, вы удаляете его с карты (это нормально), и вы должны найти новый max (в O (n)). Итак, вы делаете currentMax <- findMaxInCollection().

Если max меняется не очень часто, это чертовски хорошо, поверьте мне.

Однако не принимайте ничего как должное. Вам нужно немного потрудиться, чтобы найти лучшую комбинацию между различными структурами данных. Пройдите тесты, узнайте, как часто max меняется. Структуры данных не легки, и вы можете изменить ситуацию, если вы действительно работаете, комбинируя их, а не находите волшебную, которой не существует. :)

Приветствия