将二叉堆的大小限制为前 N 个元素

Question

我一直在研究二进制堆，它们显然是优先级队列的一个很好的数据结构。假设我的数据流有数百万 (N) 条记录，并且我定期对排名前 1000 (k << N) 条记录感兴趣。如果有足够的空间，我只需维护一个 N 大小的二进制堆，每次插入的时间复杂度为 O(log N)。不过，我想做的是在每次插入时修剪树，即丢弃第 1001 个元素。对于我来说，如何在小于 O(k) 的时间内进行修剪并不明显。

（如果我对每次修剪（和插入）的 O(k) 时间感到满意，我只需维护 k 个元素的有序列表，而不是堆。）

一种想法是有两个并行堆，一个保留最小值，另一个保留最大值，两者都只保留前 1000 个元素。不过，它有点难看。

只是为了澄清一下，这些是我的限制：

• 插入：理想情况下少于~1000次操作（因此排除原始列表）
• 存储：有限，需要大致以插入速率修剪不受欢迎的项目（一些恒定的开销是可以的）
• 查询前 1000 个：前 1000 个项目不必完全排序，堆顺序就可以

Answer 1

您可以使用二进制堆轻松完成此操作。

假设您有一个大小未知的项目流，并且您想要找到前 1,000 个项目。这是我的想法。

initialize heap
while (items to be read)
{
    read item
    if (heap.count < 1000 OR item > heap.Peek())
    {
        // Either we haven't added 1,000 items yet,
        // or the new item is larger than the smallest
        // item on the heap.
        heap.Add(item)
        if (heap.count > 1000)
        {
            // trim the heap
            // This makes sure that the heap doesn't
            // grow too large.
            heap.RemoveFirst()
        }
     }
}

（heap.Peek()检查但不删除堆上最低的项目）。

完成后，堆将包含按排名排列的前 1,000 个项目。

这不可能在 O(N) 时间内完成。该算法的复杂度为 O(N log k)，其中k是堆的大小。

顺便说一句，您也不会在 O(N) 时间内维护有序列表。

如果您可以将所有 1,000,000 个项目保留在一个数组中，则另一个选择是“快速选择”。它的运行时间为 O(N)，但我发现当 与k相比时N，堆选择技术更快。有关详细信息，请参阅理论与实践的结合。

如果您无法将所有项目保留在内存中（即您正在处理数据流），那么堆选择技术是您能做的最好的选择。您可以使用跳跃列表执行相同的操作，这也是 O(n log k)，但跳跃列表的性能可能比二进制堆稍好。

顺便说一句，O(n log k) 是最坏的情况，如果项目按排序顺序提交到堆，就会发生这种情况。在这种情况下，每个项目都会添加到堆中。如果物品分布得更正常，则大多数物品都无法通过测试heap.Peek()。我的测试表明，在正态分布的情况下，只有大约 10% 的项目（从 1,000,000 个中选择 1,000 个）通过第一个测试。同样，更多信息可以在我上面链接的博客文章中找到。