структура данных коллекции java для хранения отсортированных предметов

Question

У меня есть программа, которая использует ArrayList<T>, и этот тип T также реализует Comparable<T>. Мне нужно сохранить этот список отсортированным.

На данный момент, когда я вставляю новый элемент, я добавляю его в ArrayList, а затем вызываю Collections.sort(myArrayList).

Является ли сортировка с Collections.sort каждый раз, когда я вставляю новый элемент, серьезно повреждающий сложность времени выполнения?

Есть ли более подходящая структура данных, которую я могу использовать, чтобы всегда сортировать список? Я знаю структуру, называемую PriorityQueue, но мне также нужно иметь возможность получать элементы списка по индексу.

EDIT: В моем конкретном случае, вставляя новый элемент бывает гораздо меньше, чем адресности уже существующий элемент, так что в конечном итоге хороший совет также мог бы остаться с ArrayList, так как он получил постоянную временную сложность получения элемента , Но если вы знаете что-нибудь еще ...

Answer 1

Кажется, что Collection.Sort - это на самом деле путь сюда, поскольку коллекция уже почти отсортирована, сортировка займет не более O (n) в худшем случае.

Answer 2

Вместо того, чтобы использовать Collections.sort(myArrayList) после каждой вставки, вы можете сделать что-то более умное, как вы знаете, каждый раз, когда вы вставляете элемент, ваша коллекция уже заказана.

Collections.sort(myArrayList) принимает 0 (nlogn) раз, вы можете сделать упорядоченную вставку в упорядоченной коллекции в O (n) раз, используя Collections.binarySearch. Если коллекция упорядочена в порядке возрастания Collections.binarySearch возвращает индекс элемента, который вы ищете, если он существует, или (-(insertion point) - 1). Перед вставкой элемента вы можете искать его с Collections.binarySearch (время O (logn)). Сделано, что вы можете получить индекс, в который вставляется новый элемент. Затем вы можете добавить элемент с addAt в O (n). Вся сложность вставки ограничена addAt, поэтому вы можете сделать упорядоченную вставку в ArrayList в O (n) времени.

Answer 3

Список - это упорядоченная коллекция, что означает, что вам нужно иметь доступ с помощью индекса. Если коллекция внутренне перемещает или сортирует элементы, порядок вставки не будет таким же, как порядок элементов во внутренней структуре данных. Таким образом, вы больше не можете зависеть от доступа на основе индексов. Следовательно, Sun не предоставил класс SortedList или TreeList. Вот почему вы используете Collections.sort (..)

Коллекции коллекций Apache предоставляют класс TreeList, но он не является отсортированным списком и называется так, потому что он использует структуру данных дерева для внутреннего хранения элементов. Проверьте его документацию здесь - http://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/list/TreeList.html

Answer 4

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

Например, ArrayList для поиска по индексу и TreeMap (или очередь приоритетов) для сортировки.