获取集合中 N 个最小的 [Comparable] 项

Question

我有一个未排序的对象集合[具有可比性]，是否可以获取列表集合的子列表而无需调用排序？

我正在考虑做一个容量有限的 SortedList 的可能性，但这看起来不是正确的选择。

我可以很容易地写这个，但我想知道是否还有其他方法。

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

Answer 1

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

Guava 库（Google 的核心 Java 库）中有一些方法可以做到这一点；查看 Ordering 并查看：

• public;列表Ordering.leastOf(Iterable iterable, int k)
• public;列表Ordering.greatestOf(Iterable iterable, int k)

这些是 quickselect，并且由于它们是通用编写的，因此您只需在 Set 上调用它们即可获取 k 最小事物的列表。如果您不想使用整个 Guava 库，文档链接到源代码，我认为将方法移植到您的项目应该很简单。

如果您不想偏离标准库太远，您始终可以使用像 TreeSet 这样的排序集，尽管这会让您获得对数插入/删除时间，而不是漂亮的 O( 1)基于哈希的Set的性能，最终达到O(n log(n))。其他人提到了使用堆。这也将为您带来O(n log(n))运行时间，除非您使用一些更奇特的堆变体。 GraphMaker 中有一个 斐波那契堆实现< /a> 如果您正在寻找其中之一。

其中哪一个有意义实际上取决于您的项目，但我认为这涵盖了大部分选项。

Answer 2

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

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

Answer 3

是的，你可以将它们全部放入一个固定大小为N的最大堆数据结构中，有条件地，如果该项小于最大堆中的最大项（通过使用 get()“peek”方法检查）。一旦你这样做了，根据定义，它们将是 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_struct%29

你不想堆一堆吗？