问题描述
我有一个未分类的对象集合[可比较]，是否有可能获得列表集合的子列表而无需调用sort？
我正在考虑使用有限容量执行SortedList的可能性，但这看起来不是正确的选项。
我可以很容易地写出这个，但我想知道是否还有另一种方式。
我无法修改现有集合的结构。
1楼
由于您不想调用sort() ，因此您似乎正在尝试避免O（n log（n））运行时成本。
其实是有办法做到在O（n）的时间-您可以使用 。
在Guava库中有一些方法可以做到这一点（谷歌的核心Java库）;
查看Ordering并查看：
这些是实现，因为它们是一般编写的，你可以在你的Set上调用它们并获得k最小的东西的列表。
如果您不想使用整个Guava库，那么docs链接到源代码，我认为将方法移植到项目中应该很简单。
如果你不想偏离标准库太远，你总是可以使用像TreeSet这样的有序集，虽然这可以获得对数插入/删除时间，而不是基于散列的Set的漂亮的O（1）性能，最后它最终成为O（n log（n）） 。
其他人提到使用堆。
除非您使用一些更 ，否则这也将获得O（n log（n））运行时间。
如果你正在寻找其中一个，那么有一个 。
哪些有意义取决于您的项目，但我认为这涵盖了大多数选项。
2楼
我可能会创建一个有序集。 将未分类集合中的前N个项目插入到已排序集合中。 然后为你未分类的集合的剩余部分：
- 在排序集中插入每个项目
- 从排序集中删除最大的项
- 重复，直到您处理了未排序集合中的所有项目
3楼
是的，如果项目小于最大堆中的最大值（通过使用get() “peek”方法检查get() ，则可以将它们全部放入具有固定大小N的 。
一旦你这样做了，根据定义，它们将是最小的N.
最佳实现将以O(M)+lg(N)或O(M) （其中M是集合的大小）性能执行，这在理论上是最快的。
这是一些伪代码：
MaxHeap maxHeap = new MaxHeap(N);
for (Item x : mySetOfItems) {
if (x < maxHeap.get()) {
maxHeap.add(x);
}
}
似乎是它们的旗舰二进制堆数据结构，尝试使用那个。
4楼
你不是只想堆一堆吗？