algorithm - 将二叉堆的大小限制为前 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 相比较小时，堆选择技术更快。参见 When theory meets practice了解详情。

如果您不能将所有项目都保存在内存中(即您正在处理数据流)，那么堆选择技术是您能做的最好的。你可以用 skip list 做同样的事情，这也是 O(n log k)，但跳过列表的性能可能比二进制堆略好。

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