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

Question

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

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

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

Answer 1

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

它的构造需要O（n）的摊销时间，取10个最小元素需要O（10*log（10）），即O（1）。

Answer 2

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

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是所需的元素数。