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

我对算法理论（来自 Cormen）感到耳目一新。
二进制尝试一章中有一个练习，要求：

min-heap 属性可以用来打印 n 节点的键吗 树在 O(n) 时间内排序？展示如何做，或解释为什么不做。

我想是的，这是可能的。
在最小堆中，节点中的元素小于其两个子节点。
所以堆的根总是所有n个元素中较小的元素，根的左孩子比左子树中的所有元素小，根的右孩子比左子树中的所有元素小。右子树等

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

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

但我在解决方案中检查了这里：
Cormen 补充解决方案 http://mitpress.mit.edu/algorithms/solutions/chap12-solutions.pdf

1）它讨论了最大堆 2）它说它不能在 O(n) 时间内完成：

在堆中，节点的键是其子节点的键。在二进制中 搜索树，节点的键是其左孩子的键，但其右孩子的键 孩子的钥匙。堆属性，与二叉树不同 属性，无助于按排序顺序打印节点，因为它 不知道节点的哪个子树包含要打印的元素 在该节点之前。堆中，小于节点的最大元素 可以在任一子树中。请注意，如果堆属性可以是 用于在 O(n) 时间内按排序顺序打印键，我们将得到一个 用于排序的 O(n) 时间算法，因为构建堆只需要 准时。但我们知道（第 8 章）比较排序必须采用 (nlgn) 时间。

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

我在这里误解了什么吗？

首先，讨论中省略最小堆可能不是一个错字，我们讨论的是最小堆还是最大堆并不重要（比较器只是相反）。

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

        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 time.

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

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

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

1) 维基百科：二叉堆 http://en.wikipedia.org/wiki/Binary_heap

2) Wolfram MathWorld：堆 http://mathworld.wolfram.com/Heap.html这里的堆对于理解为什么它不是线性操作特别有帮助。