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

Question

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

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

我不确定作者的意思是什么.当他们说"广度优先搜索"时,首先想到的是从根开始的树元素的广度优先搜索,但是不能保证按排序顺序列出元素,也不需要采用对数时间每个元素.例如,无论你如何打破关系,在这个最小堆上运行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

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