6

我目前正在阅读这篇论文,在第五页,它讨论了它认为是常识的二进制堆的属性。然而,他们提出的观点之一是我以前从未见过并且无法理解的东西。作者声称,如果给定一个平衡的二叉堆,则可以使用标准的广度优先搜索在每个元素 O(log n) 时间内按排序顺序列出该堆的元素。这是他们的原话:

在平衡堆中,任何新元素都可以在对数时间内插入。我们可以按权重顺序列出堆中的元素,只需使用广度优先搜索,就可以用对数时间来生成每个元素。

我不确定作者的意思是什么。当他们说“广度优先搜索”时,首先想到的是从根开始对树元素进行广度优先搜索,但这不能保证按排序顺序列出元素,也不需要对数时间每个元素。例如,在这个最小堆上运行 BFS 会产生乱序的元素,无论你如何打破关系:

             1
            / \
          10   100
         /  \
        11  12

这总是在 11 或 12 之前列出 100,这显然是错误的。

我错过了什么吗?是否有一个简单的广度优先搜索,您可以在堆上执行以使用对数时间按排序顺序取出元素?显然,您可以通过每次删除最小元素来破坏性地修改堆来做到这一点,但作者的意图似乎是这可以非破坏性地完成。

4

2 回答 2

5

您可以通过使用优先级队列(需要另一个堆!)遍历堆来按排序顺序取出元素。我想这就是他所说的“广度优先搜索”。

我认为您应该能够弄清楚(考虑到您在算法中的代表),但基本上优先级队列的关键是节点的权重。您将堆的根推入优先级队列。然后:

while pq isn't empty
    pop off pq
    append to output list (the sorted elements)
    push children (if any) onto pq

我不太确定(完全)这是否是他所指的,但它模糊地符合描述并且没有太多活动,所以我想我不妨把它放在那里。

于 2011-08-28T11:59:55.933 回答
0

如果你知道所有低于 100 的元素都在左边,你可以向左走,但无论如何,即使你到达 100,你也可以看到左边没有元素,所以你出去。在任何情况下,在您意识到没有要搜索的元素之前,您最坏的情况是从节点(或任何其他节点)出发两次。比你进入这棵树的人最多 2*log(N) 次。这简化为 log(N) 复杂度。

关键是,即使您“搞砸”并且遍历到“错误”节点,您最坏的情况也会去该节点一次。

编辑
这就是堆排序的工作方式。您可以想象,每次取出顶部元素时,您都必须使用 N(log n) 复杂度来重建堆。

于 2011-08-27T01:00:09.393 回答