java - 从大量输入中获取排序列表(有限长度)的最佳方法是什么

Question

假设我有 1 亿个 Comparable 作为流输入，我想输出该输入的前 100 个(按顺序——我想如果你能找到前 100 个是微不足道的100).我假设某种插入排序是最好的，但实现它的最佳方法是什么(如果它是最好的方法)？

限制是您肯定会看到每个对象，一次一个(而且我绝对不能将整个集合放入内存中)。

我在想两种可能的解决方案:

1) 一个简单的链表。因此，当前 100 个对象进入时，它们将被排序(需要 O(n) 时间——但 n = 100)。然后当每个连续的对象进来时，它会被正确插入(同样是 O(n)，n = 100，时间)，如果插入，它会踢出尾部(否则，如果超过最大值，链表将保持不变值)。

2) 使用堆。我想我可以保留一个堆，插入堆，然后如果堆的大小超过我的最大元素数(在我的例子中为 100)，则丢弃根节点(堆的顶部)。这应该意味着 O(lg(n)) 运行时间，对吧？既然元素的插入和根的删除都是O(lg(n))，对吧？

Java 中是否有适合堆的库？我真的不想编写自己的堆结构。

附注

如果您想知道我为什么这样做，那是为了梦幻足球。我有一个程序可以在薪水上限的约束下找到一组球员的最大投影点(这是一种蛮力算法)。事实上，这完全是另一个问题，即如何解决背包问题，您必须拥有一定数量的不同类型的元素(即 1 QB、3 WR、2 RB、1 TE、1 K , 和 1 防御)。

所以我有一大组 (1,234) 球队，它们给出了最低的预计分数，但现在我正试图找到拥有广泛不同球员的球队组。我认为一组三个团队可以合理地解决(通过蛮力):1,234 选择 3 = 312,419,184(根据我的计算，这大约需要一个半小时来处理)。我将一组球队的方差计算为一名球员在每支球队中出现的次数(因此值越低，球队组的方差越高)。

Answer 1

如果您所做的只是添加，则可以使用它。

public static <T> SortedSet<T> topValues(final int n, final Comparator<T> comparator) {
    return new TreeSet<T>(comparator) {
        @Override
        public boolean add(T t) {
            // if less than N in size, just try to add it.
            if (super.size() < n)
                return super.add(t);

            T first = super.first();
            // if smaller than the first, discard it.
            if (comparator.compare(t, first) <= 0)
                return false;
            // otherwise try to add it.
            super.remove(first);
            super.add(t);
            return true;
        }
    };
}

或者如果类型已经是 Comparable

public static <T extends Comparable<T>> SortedSet<T> topValues(final int n) {
    return new TreeSet<T>() {
        @Override
        public boolean add(T t) {
            // if less than N in size, just try to add it.
            if (super.size() < n)
                return super.add(t);

            T first = super.first();
            // if smaller than the first, discard it.
            if (t.compareTo(first) <= 0)
                return false;
            // otherwise try to add it.
            super.remove(first);
            super.add(t);
            return true;
        }
    };
}

只需将所有值添加到这个集合中，它将只有 n 个值，每次都丢弃最小的一个。