假设我想从任意数量的记录中找到最低的 10 个值。当我循环记录时,我将它们添加到结构中,直到达到最大大小 10。此后,每次添加不高于列表中最高记录的记录时,将使用当前最高记录被删除,保留最大记录数。
或者更简单地说,如何处理(可能非常大)对象列表并以节省内存的方式仅保留特定数量的对象?
我似乎记得有某种数据结构可以做到这一点,但显然我在谷歌搜索方面做得很差。我假设无论它是什么结构都会在某个地方有一个 java 实现。
最佳答案
如果您愿意将所有 N 个值保留在内存中,则可以使用二进制最小堆对数组进行堆化。
其构造需要 O(n) 摊销时间,并且获取 10 个最小元素需要 O(10*log(10)),即 O(1)。
关于java - 我不记得固定大小的排序树的数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11782724/