我目前正在阅读这篇论文,在第五页,它讨论了它认为是常识的二进制堆的属性。然而,他们提出的观点之一是我以前从未见过并且无法理解的东西。作者声称,如果给定一个平衡的二叉堆,则可以使用标准的广度优先搜索在每个元素 O(log n) 时间内按排序顺序列出该堆的元素。这是他们的原话:
在平衡堆中,任何新元素都可以在对数时间内插入。我们可以按权重顺序列出堆中的元素,只需使用广度优先搜索,就可以用对数时间来生成每个元素。
我不确定作者的意思是什么。当他们说“广度优先搜索”时,首先想到的是从根开始对树元素进行广度优先搜索,但这不能保证按排序顺序列出元素,也不需要对数时间每个元素。例如,在这个最小堆上运行 BFS 会产生乱序的元素,无论你如何打破关系:
1
/ \
10 100
/ \
11 12
这总是在 11 或 12 之前列出 100,这显然是错误的。
我错过了什么吗?是否有一个简单的广度优先搜索,您可以在堆上执行以使用对数时间按排序顺序取出元素?显然,您可以通过每次删除最小元素来破坏性地修改堆来做到这一点,但作者的意图似乎是这可以非破坏性地完成。