java - 我不记得固定大小的排序树的数据结构

Question

假设我想从任意数量的记录中找到最低的 10 个值。当我遍历记录时，我将它们添加到结构中，直到它达到我的最大大小 10。之后，每次我添加一个不高于列表中最高记录的记录时，当前最高删除保留最大记录数。

或者更简单地说，我如何处理一个（可能非常大的）对象列表，并且只以内存有效的方式保留特定数量的对象？

我似乎记得有某种数据结构可以做到这一点，但显然我在谷歌搜索方面做得很差。我假设它的任何结构都会在某个地方有一个 java 实现。

Answer 1

如果您愿意将所有 N 个值保留在内存中，则可以使用二进制最小堆来堆化数组。

它的构造需要 O(n) 的摊销时间，最少 10 个元素需要 O(10*log(10))，即 O(1)。

Answer 2

一个简单的方法是实现一个最大堆（例如二进制堆）并执行以下操作（伪代码啊！）：

List elms; // original elements
Heap heap; // heap we store in

for element e in elms:
    push e onto heap
    if heap contains more than 10 elements:
        pop the max element from heap

在此之后，heap将包含 10 个最小的元素。

假设一个二进制堆，tihs 需要O(k)额外的空间和O(n lg k)时间，k你想要的元素数量在哪里。