c++ - 如何在有限的空间中选择最少的 N 个元素？

Question

问题:

函数 f 以未知顺序一次返回一个元素。我想选择最少的 N 元素。函数 f 被调用了很多次(我在一个非常复杂的搜索空间中搜索)，我没有足够的内存来存储每个输出元素以供将来排序。

显而易见的解决方案:

在内存中保留一个 N 元素的 vector ，并在每个 f() 上搜索最小值和最大值，并可能替换一些东西。这可能适用于非常小的 N。不过，我正在寻找更通用的解决方案。

我目前的解决方案:

我考虑使用 priority_queue 来存储比方说 2N 值，并在每个 2N 步骤后减少上半部分。

伪代码:

while (search goes on)
    for (i=0..2N)
        el = f()
        pust el to the priority queue
    remove N greatest elements from the priority queue
select N least elements from the priority queue

我认为这应该可行，但是，我觉得它一点也不优雅。也许已经有某种数据结构可以处理这个问题。如果只是修改 priority_queue 以丢弃不适合保存范围的元素，那就太好了。

您能否向我推荐一个现有的 C++ std 数据结构，或者鼓励我实现上面建议的解决方案？或者也许有一些我想不到的伟大而优雅的技巧。

Answer 1

您想从调用函数得到的总 K 个元素中找到最少的 n 个元素。每次调用函数 f() 时，您都会得到一个元素，并且您希望在其中存储 least n 个元素，而不存储从中获得的总 k 个元素k 之后的函数太大了。

您可以定义一个heap 或priority_queue 来存储目前找到的这个least n。只需将 f() 的返回项添加到 pq 中，并在其大小变为 n+1 时弹出最大的元素。

总复杂度为 O(K*log(n))，所需空间为 O(n)。 (如果我们忽略 pq 所需的一些额外空间)