algorithm - 使用堆属性按排序顺序打印树 (Cormen)

Question

我正在刷新算法理论(来自 Cormen)。
在二进制尝试的章节中有一个练习要求:

Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Show how, or explain why not.

我认为是的，这是可能的。
在最小堆中，节点中的元素小于其两个子节点。
所以堆的根始终是所有 n 个元素中较小的元素，根的左 child 小于左子树中的所有元素，根的右 child 小于左子树中的所有元素右子树等

因此，如果继续提取根，打印它，然后用较小的子节点更新根，我们将保留最小堆属性，并按排序顺序打印。 (我正在考虑一个不是基于数组的最小堆)。

所以这可以在 O(n) 时间内完成，因为要更新根，我们只需比较 2 个 child 并将根的指针更新为 2 中较小的一个。

但我在解决方案中检查了这里:
Cormen Supplement Solutions

并且 1) 它谈论最大堆 2) 它说它不能在 O(n) 时间内完成:

In a heap, a node’s key is both of its children’s keys. In a binary search tree, a node’s key is its left child’s key, but its right child’s key. The heap property, unlike the binary-searth-tree property, doesn’t help print the nodes in sorted order because it doesn’t tell which subtree of a node contains the element to print before that node. In a heap, the largest element smaller than the node could be in either subtree. Note that if the heap property could be used to print the keys in sorted order in O(n) time, we would have an O(n)-time algorithm for sorting, because building the heap takes only O(n) time. But we know (Chapter 8) that a comparison sort must take (n lg n) time.

从我的角度来看，我可以理解使用最大堆，不可能在 O(n) 中打印它们。
但是，根据我解释的推理，是否可以使用 min-heap 属性来做到这一点？
还有为什么解决方案会忽略最小堆。是错字还是错误？

我是不是误解了什么？

Answer 1

首先，讨论中省略最小堆可能不是错字，我们谈论的是最小堆还是最大堆并不重要(比较器只是颠倒了)。

仅提取根然后用其两个子树中较小的一个替换的问题在于，不能保证左子树小于右子树中的所有节点(反之亦然)。考虑以下堆

        1
       / \
      4   6
     /\   /\
    5  8 9  7

打印 1 后，您必须重新堆化，也就是说您提取 1 并将其替换为最后一行中的最后一个元素，在本例中为 7 。然后，只要需要将堆返回到正确状态，就可以切换

take away root and last node to root
        7
       / \
      4   6
     /\   /
    5  8 9

swap
        4
       / \
      7   6
     /\   /
    5  8 9

swap
        4
       / \
      5   6
     /\   /
    7  8 9

所有这些交换都会花费您 log n 时间。

如果您将根节点替换为 4，您仍然需要通过左分支重新堆化结构，从而增加提取根节点的线性成本的成本。如果堆看起来像这样会怎样

        1
       / \
      4   9
     /\   /\
    5  6 11 15
   /\
  8  7

我查看的形成解决方案的页面

1) Wikipedia: binary heap

2) Wolfram MathWorld: heap这里的堆特别有助于理解为什么它不是线性操作。