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

假设我想从任意数量的记录中找出最低的10个值。当我遍历记录时，我将它们添加到结构中，直到它达到我的最大大小为10.之后，每次添加一个不高于列表中最高记录的记录时，当前最高被删除保留最大数量的记录。或者更简单地说，我该如何处理一个（可能非常大的）对象列表，并且只以一种有效的内存方式保存特定数量的对象？我不记得固定大小排序树的数据结构

我似乎记得有某种数据结构可以做到这一点，但显然我在Google上做的不好。我假设它的任何结构都会有一个java实现。

来源

2012-08-02 Dave Novelli

你可能可以调整一个'PriorityQueue'来获得你要找的东西。 – 2012-08-02 17:30:25

不完全是我想到的（10年前的数据结构类有点模糊），但是这应该会有效果！谢谢 – 2012-08-02 17:49:04

这就是说，塞巴斯蒂安的答案是一个亲密的表弟（'PriorityQueue'由一个堆支持） – 2012-08-02 17:51:40

一个简单的方法来做到这将是实现一个max-heap（一binary heap，例如），并执行以下操作（伪代码啊嗬！）：

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是您想要的元素数。

来源

2012-08-02 17:43:16

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

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

来源

2012-08-03 20:12:10

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

回答

相关问题