获取集合中N个最小的项目

我有一个未分类的对象集合[可比较]，是否有可能获得列表集合的子列表而无需调用排序？

我正在考虑使用有限容量执行SortedList的可能性，但这看起来不是正确的选项。

我可以很容易地写这个，但我想知道是否还有另一种方式。

我无法修改现有集合的结构。

Answer 1

由于您不想调用sort() ，因此您似乎正在尝试避免O（n log（n））运行时成本。 实际上有一种方法可以在O（n）时间内完成 – 你可以使用选择算法 。

在Guava库中有一些方法可以做到这一点（谷歌的核心Java库）; 查看Ordering和退房：

• public List Ordering.leastOf(Iterable iterable, int k)
• public List Ordering.greatestOf(Iterable iterable, int k)

这些是quickselect的实现，因为它们是一般编写的，你可以在你的Set上调用它们并获得k最小的东西的列表。 如果您不想使用整个Guava库，那么docs链接到源代码，我认为将方法移植到项目中应该很简单。

如果你不想偏离标准库太远，你总是可以使用像TreeSet这样的有序集合，虽然这可以获得对数插入/删除时间而不是基于散列的Set的漂亮的O（1）性能，最后它最终成为O（n log（n）） 。 其他人提到使用堆。 除非您使用一些更高级的堆变体 ，否则这也将获得O（n log（n））运行时间。 如果你正在寻找其中一个，那么GraphMaker中有一个斐波纳契堆实现 。

哪些有意义取决于您的项目，但我认为这涵盖了大多数选项。

Answer 2

我可能会创建一个排序集。 将未分类集合中的前N个项目插入到已排序集合中。 然后，对于未分类的集合的剩余部分：

1. 在排序集中插入每个项目
2. 从排序集中删除最大的项
3. 重复，直到您处理了未排序集合中的所有项目

Answer 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); } } 

Apache Commons Collections类的PriorityBuffer似乎是它们的旗舰二进制堆数据结构，尝试使用那个。

Answer 4

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

你不是只想做一堆吗？