Java 用于保持项目排序的集合数据结构

a collection data structure to keep items sorted

提问by Yonatan Nir

I got a program which is using an ArrayList<T>and that type T also implements Comparable<T>. I need to keep that list sorted.

我有一个程序正在使用ArrayList<T>并且该类型 T 也实现了Comparable<T>. 我需要保持该列表排序。

For now, when I insert a new item, I add it to the ArrayListand then invoke Collections.sort(myArrayList).

现在，当我插入一个新项目时，我将它添加到 中ArrayList，然后调用Collections.sort(myArrayList).

Is sorting with Collections.sortevery time I insert a new item seriously hurt run time complexity?

Collections.sort每次插入新项目时进行排序会严重损害运行时复杂性吗？

Is there a better suited data structure I can use to always keep the list sorted? I know of a structure called a PriorityQueuebut I also need to be able to get the list's elements by index.

是否有更合适的数据结构可以用来始终保持列表排序？我知道一个名为 a 的结构，PriorityQueue但我还需要能够通过索引获取列表的元素。

EDIT: In my specific case, inserting a new item happens much less than geting an already existing item, so eventually a good advice could also be to stay with the ArrayListsince it got a constant time complexity of getting an item. But if you know of anything else...

编辑：在我的特定情况下，插入一个新项目比获得一个已经存在的项目要少得多，所以最终一个好的建议也可能是保持ArrayList不变，因为它获得一个项目的时间复杂度是恒定的。但如果你知道其他任何事情......

采纳答案by Yonatan Nir

It seems like Collection.Sortis actually the way to go here since when the collection is already almost sorted, the sorting will take not longer than O(n) in the worst case.

看起来Collection.Sort实际上是这样的方式，因为当集合已经几乎排序时，排序在最坏的情况下不会超过 O(n)。

回答by mziccard

Instead of using Collections.sort(myArrayList)after every insertion you might want to do something a bit smarter as you know that every time you insert an element your collection is already ordered.

而不是Collections.sort(myArrayList)在每次插入后使用，您可能想要做一些更聪明的事情，因为您知道每次插入一个元素时，您的集合已经被排序。

Collections.sort(myArrayList)takes 0(nlogn) time, you could do an ordered insert in an ordered collection in O(n) time using Collections.binarySearch. If the collection is ordered in ascending order Collections.binarySearchreturns the index of the element you are looking for if it exists or (-(insertion point) - 1). Before inserting an element you can look for it with Collections.binarySearch(O(logn) time). Done that you can derive the index at which inserting the new element. You can then add the element with addAtin O(n) time. The whole insertion complexity is bounded by the addAtso you can do an ordered insert in an ArrayList in O(n) time.

Collections.sort(myArrayList)需要 0(nlogn) 时间，您可以使用Collections.binarySearch. 如果集合按升序排列，则Collections.binarySearch返回您要查找的元素的索引（如果它存在）或(-(insertion point) - 1)。在插入元素之前，您可以使用Collections.binarySearch(O(logn) 时间)查找它。完成后，您可以导出插入新元素的索引。然后您可以addAt在 O(n) 时间内添加元素。整个插入复杂度受 限制，addAt因此您可以在 O(n) 时间内在 ArrayList 中进行有序插入。

回答by Raman Shrivastava

List is an ordered collection, which means you need to have the ability to access with index. If a collection internally shuffles or sorts the elements, the insertion order wont be same as the order of the elements in the internal data structure. So you cannot depend on index based access anymore. Hence Sun didn't provide a SortedList or a TreeList class. That is why you use Collections.sort(..)

List 是一个有序的集合，这意味着你需要有索引访问的能力。如果集合在内部对元素进行混洗或排序，则插入顺序将与内部数据结构中元素的顺序不同。所以你不能再依赖基于索引的访问了。因此 Sun 没有提供 SortedList 或 TreeList 类。这就是为什么你使用 Collections.sort(..)

Apache commons-collections does provide a TreeList class but it is not a sorted List and is called so because it uses a tree data structure to store the elements internally. Check its documentation here - http://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/list/TreeList.html

Apache commons-collections 确实提供了一个 TreeList 类，但它不是一个排序的 List，之所以这样称呼是因为它使用树数据结构在内部存储元素。在此处查看其文档 - http://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/list/TreeList.html

回答by Amber Beriwal

A single data structure cannot provide both sorting and index based retrieval. If the input set is limited to a few hundreds or thousands, you can keep two data structures in parallel.

单个数据结构不能同时提供排序和基于索引的检索。如果输入集限制在数百或数千个，则可以并行保留两个数据结构。

For example, ArrayListfor index based retrieval and TreeMap(or priority queue) for sorting.

例如，ArrayList用于基于索引的检索和TreeMap（或优先级队列）用于排序。