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

Question

我对算法理论很感兴趣(来自Cormen).
本章中有一个针对二进制尝试的练习,询问:

可以使用min-heap属性在O(n)时间内按排序顺序打印出n节点树的键吗？展示如何,或解释为什么不.

我想是的,这是可能的.
在最小堆中,节点中的元素小于其子节点.
因此堆的根始终是所有n个元素中较小的元素,并且根的左子节点小于左子树中的所有元素,并且根的右子节点小于所有元素中的所有元素.正确的子树等

因此,如果我们继续使用root,打印它,然后使用较小的子进程更新root,我们保留min-heap属性,并按排序顺序打印.(我在考虑一个不基于数组的最小堆).

所以这可以在O(n)时间内完成,因为更新根,我们只是比较2个子节点并将根指针更新为2中的较小者.

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

1)它谈论max-sheaps 2)它说它不能在O(n)时间内完成:

在堆中,节点的密钥是其子密钥.在二叉搜索树中,节点的键是其左子键,但是右子键.与binary-searth-tree属性不同,heap属性无法按排序顺序打印节点,因为它不会告诉节点的哪个子树包含要在该节点之前打印的元素.在堆中,小于节点的最大元素可以在任一子树中.请注意,如果可以使用堆属性在O(n)时间内按排序顺序打印密钥,那么我们将使用O(n)-time算法进行排序,因为构建堆只需要O(n)时间.但我们知道(第8章)比较排序必须花费(n lg n)时间.

从我的角度来看,我可以理解使用max-heap,无法在O(n)中打印它们.
但是,根据我解释的推理,使用min-heap属性是不是可以做到这一点？
另外,为什么解决方案会忽略min-heap.是拼写错误还是错误？

我在这里误会了什么吗？

Answer 1

首先,在讨论中遗漏min-sheaps可能不是一个错字,如果我们谈论的是最小堆或最大堆(比较器刚好被颠倒),这并不重要.

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

        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)维基百科:二进制堆

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