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

Question

我一直在学习二叉堆，显然它是一个优先队列的好数据结构。假设我的数据流有数百万条（N）记录，我定期对排名前1000 (k << N) 的记录感兴趣。如果有足够的空间，我会维护一个大小为 N 的二叉堆，每次插入的复杂度都是 O (log N)。不过，我希望在每次插入时剪枝树，即丢弃第1001个元素。但是我并不清楚如何在少于O(k)的时间内进行剪枝。

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

一个想法是使用两个平行堆，一个保留最小值，另一个保留最大值，两个堆都只保留前1000个元素。不过这有点丑陋。

仅澄清一下，这些是我的限制条件：

- 插入：理想情况下少于~1000个操作（因此不适用原始列表） - 存储：有限的需要以插入速率大约剪枝不受欢迎的项目（某些恒定的开销是可以接受的） - 询问前1000名：前1000名不必完全排序，堆式顺序可以

- Steve Howell

---

你能把你的问题表述得更清楚一些吗？（提示：问题以问号结尾） - PengOne

如果您使用选择算法，在每k步（k = 1000是要选择的项目数）之后进行修剪，那么每次插入的时间复杂度为O(1)。（这是一条注释，因为您指定了每个步骤。） - Per

基本上，可以这样说：

• 平衡二叉树非常适合动态情况下需要随时间保留前1000个项目，并且需要经常查询它们的情况。
• 最小最大堆克服了简单最小堆的一些限制。
• 对于更静态的情况，您只需从大型数据集中获取前1000个项目，实际上使用倒置堆，其中头元素不再是“最佳”项目，而是头元素是通往前1000个项目的门卫，排序被反转，以便“更好”的项目更深入。

- Steve Howell

拥有一个2047项的二叉堆不足以满足需求吗？当你添加新项目时，如果堆已经满了，只需用要插入的项目替换最后一个（第2047个）元素即可。 - Antti Huima

Answer 1

你可以使用二叉堆轻松完成此操作。

假设你有一个大小未知的项目流，并且想要找到前1000个项目。以下是思路。

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)时间内维护有序列表。

另一个选择是使用Quickselect，如果您可以将所有1,000,000个项目保存在数组中。 它以O(N)时间运行，但是我发现当k相对于N很小时，堆选择技术更快。 有关详细信息，请参见When theory meets practice。

如果您无法将所有项目保存在内存中（即，您正在使用数据流），那么堆选择技术是您能做的最好的选择。您可以使用跳表完成相同的操作，其复杂度也为O(n log k)，但跳表可能比二叉堆表现略好。

顺便说一下，O(n log k)是最坏情况，即如果项目按排序顺序呈现给堆，则会发生这种情况。在这种情况下，每个项目都会被添加到堆中。如果项目分布更正常，则大多数项目都无法通过heap.Peek()测试。我的测试显示，在正常分布的情况下，仅有约10％的项目（从100万个项目中选择1000个）通过了第一个测试。同样，更多信息可在我上面链接的博客文章中获得。

- Jim Mischel

---

@Saeed：在最小堆中，你可以在O(1)时间内找到最小的项。 - Jim Mischel

@Jim，我同意你的观点，最小堆可以高效地获取k个顶部项目，但是最小堆的问题在于如何防止它的大小超出了前k个值太远。 - Steve Howell

吉姆，我认为我们在测量不同的东西。如果我要保持有序列表，每个插入将是O(k)，所以你正确，N个插入将是O(n * k)。 - Steve Howell

Jim，你的解决方案唯一的问题是堆有点颠倒了。如果我想要查询最大的项目，那将会很昂贵。（在我的原始帖子中，这就是拥有两个堆的想法背后的原因。一个堆将使跟踪传统顺序中的“最佳”项目变得容易；另一个堆将使识别掉出前1000个项目变得容易。） - Steve Howell

@SteveHowell：你没有明确说明你需要保留掉落的物品。如果你想要保留它们，那么你需要一个额外的数据结构。至于堆是倒序的问题，你可以复制底层数组并反转它（一个O(k)的操作），如果你真的需要以某种顺序获取这些物品。然而，请注意，堆可能会变得非常不平衡（小的元素在叶子节点），所以“类似堆”的顺序对你没有太大帮助。一般来说，堆是一个糟糕的用于查询的数据结构。如果你需要查询，那么跳表（首选）或平衡树会更好。 - Jim Mischel

Answer 2

听起来你需要一个最小-最大堆。

这可以为删除最小值和最大值提供O(log(n))的操作，这应该可以帮助你实现你的目标。

- Peter Alexander

---

请问您能否澄清一下，您希望如何使用最小-最大堆来保留前1000个元素？ - Saeed Amiri

@SaeedAmiri，创建一个包含前1000个元素的最小-最大堆。对于之后的每个元素x，如果x > heap.min，则删除heap.min并将x添加到堆中。最终在堆中留下前1000个元素；为了按顺序提取它们，需要提取1000次heap.max。 - James Waldby - jwpat7

Peter，Min-Max论文很棒。我相信这正好回答了我的问题。谢谢！ - Steve Howell

@jwpat7，真的我不明白你想找什么？假设k=2，你有一个包含10个项目的列表，请尝试用纸和笔做你想做的事情。 - Saeed Amiri

假设n=7，k=3，x=(7,3,4,8,1,5,6)。将h初始化为7,3,4，得到{7,3,4}。测试8>3，删除3，添加8，h={8,7,4}。测试1>4。测试5>4，删除4，添加5，h={8,7,5}。测试6>5。删除5，添加6，h={8,7,6}。 - James Waldby - jwpat7

虽然这解决了问题，但我不明白为什么需要一个min-max堆，当一个简单的min堆可以很好地解决问题。 - Jim Mischel

Answer 3

堆不适合用于搜索项目，也不能保持元素的顺序以保留前1000个元素，您可以使用平衡二叉搜索树在O(n)中完成此操作。

编辑：使用最小堆获取最大项的想法也足够好，我之前不知道这一点，但我更喜欢BST。

- Saeed Amiri

---

@Jim Mischel，您提供的链接是选择算法，与堆无关。此外，要从n个元素创建k个顶部节点的平衡搜索树，需要O（n log k）而不是O（n log n）。由于OP问题中的k不大，logK是常数（这里是10）。我提供了这个解决方案，因为它比选择算法更简单，特别是在不同语言中提供的类的情况下。 - Saeed Amiri

此外，你的回答说可以使用平衡树在O(n)时间内完成。这是不正确的。只有在建立树之后才能在O(n)时间内完成。 - Jim Mischel

我正在进行负评，因为堆对于能够在特定情况下获取前1000个项目非常有效。这里的限制是存储。问题的关键部分是修剪。 - Steve Howell

@SaeedAmiri 你的回答措辞有点让我困惑。当你说“堆不适合搜索项目”时，我认为你只是在说它不容易指向第1001个元素，这一点我同意。 - Steve Howell

@SteveHowell：如果你向一个已经有1,000个项目的小根堆中添加一个项目，那么第1001个项目就是堆的最小项——即树的根。删除最小项是其中的一项基本操作。它可以在O(1)时间内定位（因此为heap.Peek），并且可以在O(log k)时间内删除。 - Jim Mischel