使用堆的属性按排序顺序打印树（Cormen）

Question

我正在复习算法理论（来自Cormen）。章节中有一个关于二叉树的练习题，问：

“最小堆属性是否可以用于在O(n)时间内按排序顺序打印n个节点树的键？说明如何做到，或者为什么不行。”

我认为是可以的。在最小堆中，节点中的元素比其两个子节点都要小。因此，堆的根始终是所有n个元素中较小的元素，而根的左子节点比左子树中的所有元素都小，右子节点比右子树中的所有元素都小，以此类推。

因此，如果我们不断提取根、打印它，然后使用其子节点中较小的一个更新根，就可以保持最小堆属性并按排序顺序打印。 （我想的是不基于数组的最小堆）。

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

但是我在这里检查了解决方案： Cormen Supplement Solutions 它谈到了最大堆，并且说不能在O(n)时间内完成：

在堆中，节点的键是其两个子节点的键。在二叉搜索树中，节点的键是其左子节点的键，但是右子节点的键。堆属性不像二叉搜索树属性那样有助于按排序顺序打印节点，因为它不能告诉我们节点之前包含要打印的元素的哪个子树。在堆中，小于该节点的最大元素可能在任一子树中。请注意，如果堆属性可以用于在O(n)时间内按排序顺序打印键，则我们将拥有一个O(n)时间算法来进行排序，因为构建堆仅需要O(n)时间。但是我们知道（第8章）比较排序必须花费（n lg n）时间。

从我的角度来看，我可以理解使用最大堆无法在O(n)时间内打印它们。但是，使用我解释的最小堆属性是否可能做到呢？此外，为什么解决方案忽略了最小堆。这是笔误还是错误？

我是否有什么误解？

- Cratylus

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) 维基百科：二叉堆

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

- Matti Lyra

---

最小的渐近时间复杂度是 O(n*log(n)) 吗？ - richardaum

Answer 2

考虑使用数组表示最小堆。您将最小值放在根节点。提取根节点并用最后一个数组元素替换它，即用最低不完整“行”中的最后一个叶子替换它。执行MIN-HEAPIFY操作（显然与CLRS MAX-HEAPIFY相同，但比较方式相反）。这需要O(log n)的时间，结果是第二小的元素在根节点。重复此过程直到堆为空。这会给出一个排序的序列。

因此，该算法的复杂度为

log (n) + log (n-1) + log (n-2) + ... + 1 <= n*log n

即O(n*log n)

这是可以预料的，否则我们将得到一个比O(nlogn)复杂度更低的基于比较的排序算法，而这是不可能的。

- chill

Answer 3

我猜你的想法基本上是，对于一个堆（考虑最小堆），它的根节点是最小的元素。现在对于第二个最小的元素，左子树和右子树都具有最小堆属性，因此我们可以简单地比较左右子节点以找到第二个最小的元素。同样的方法可以继续下去...所以时间复杂度是O(n)吗？

你忽略了一个问题，随着每一层的增加，要比较的元素数量也在增加...

对于最小值-0次比较（根是最小的） 对于第二个最小值-1次比较（左子树或右子树的根） 假设左子树的根节点比右子树的根节点小。 对于第三个最小值-2次比较（右子树的根或左子树的两个子节点之一）。

你在计算渐进时间复杂度时忽略了这个比较部分。

- user3677293