algorithm - 使用广度优先搜索按排序顺序列出二进制堆中的值？

Question

我正在阅读 this paper在第五页，它讨论了它认为是常识的二叉堆的属性。然而，他们提出的其中一个观点是我以前从未见过也无法理解的。作者声称，如果给定一个平衡二叉堆，您可以使用标准的广度优先搜索在每个元素的 O(log n) 时间内按排序顺序列出该堆的元素。这是他们的原始措辞:

In a balanced heap, any new element can be inserted in logarithmic time. We can list the elements of a heap in order by weight, taking logarithmic time to generate each element, simply by using breadth first search.

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

             1
            / \
          10   100
         /  \
        11  12

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

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

Answer 1

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

我认为您应该能够弄清楚(根据您在算法方面的代表)，但基本上优先级队列的关键是节点的权重。您将堆的根插入优先级队列。然后:

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

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