打印的排序顺序使用堆属性树（Cormen） [英] Print a tree in sorted order using heap properties (Cormen)

问题描述

我耳目一新的算法理论（从Cormen）。
有一个锻炼的章节二进制尝试，询问：

I am refreshing on algorithm theory (from Cormen).
There is an exercise in the chapter for binary tries that asks:

可以最小堆属性可以用来打印出一个n个节点的密钥   树排序顺序为O（n）的时间？说明如何，或解释原因。

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个元素的小元件和根的左孩子比所有在左子树和根的右子是小于所有在的元素的元素的小右子树等。

I thought yes it is possible.
In the min heap the element in a node is smaller than both its children.
So the root of the heap is always the smaller element of all the n elements and the left child of the root is the smaller than all the elements in the left subtree and the right child of the root is the smaller than all the elements in the right subtree etc.

所以，如果让我们exracting根，打印出来，然后用其子的小更新的根，我们保持最小堆属性，我们的排序顺序打印。 （我想最小堆基础不是阵列）。

So if keep we exracting the root, print it and then update the root with the smaller of its children we keep the min-heap property and we print in sorted order. (I am thinking of a min heap that is not array based).

所以这可能在O（n）的完成时间，因为更新的根，我们只是比较的2名儿童和更新根的指针是2的小。

So this could be done in O(n) time since to update the root, we just compare the 2 children and update the root's pointer to be the smaller of the 2.

不过，我检查这里的解决方案：
Cormen补充解决方案

But I checked here in the solution:
Cormen Supplement Solutions

1）它谈论最多-堆2）它说，它无法在O完成（n）时间：

And 1)it talks about max-heaps 2) it says it can not be done in O(n) time:

在一个堆，一个节点的关键是它的两个孩子的钥匙。在二元   搜索树，一个节点的关键是它的左孩子的关键，但其右   孩子的关键。堆属性，不同的是二进制searth树   财产，不利于打印有序的节点，因为它   不知道哪一个节点的子树中包含的元素打印   在这之前的节点。在一个堆，最大的元素比节点更小   可以在任一子树。请注意，如果堆属性可以是   用来在O（n）时间打印在有序的钥匙，我们将有一个   为O（n） - 时间的算法进行排序，因为只有建立堆取   准时。但我们知道（第8章），一个比较排序必须采取   （N LG 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）。
但是，是不是可以用最小堆属性我解释的理由办呢？
还有为什么该解决方案忽略最小堆。它是一个错字或错误？

From my point of view I can understand that using a max-heap, it is not possible to print them in O(n).
But isn't it possible to do it using the min-heap property for the reasoning I explained?
Also why does the solution ignore the min-heap. Is it a typo or error?

我是不是misundertanding一些东西呢？

Am I misundertanding something here?

推荐答案

首先遗漏最小堆在讨论的可能不是一个错字，它其实并不重要，如果我们谈论的是一个最小堆或最大堆（比较刚好相反）。

Firstly the omission of min-heaps in the discussion probably isn't a typo, it doesn't really matter if we're talking about a min heap or a max heap (the comparator is just reversed).

只提取所述根，然后与它的两个孩子的小更换的问题是，左孩子不能保证是比在右子树（和反之亦然）的所有节点小。考虑下面的堆

The problem with only extracting the root and then replacing with the smaller of its two children is that the left child is not guaranteed to be smaller than all the nodes in the right subtree (and vice verse). Consider the following heap

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

印刷后的 1 你必须reheapify这是说你提取 1 ，并将其与最后一个元素替换最后一排，在这种情况下 7 。然后，切换，只要你需要返回堆到它的正确状态

After printing 1 you have to reheapify which is to say you extract 1 and replace it with the last element in the last row, in this case 7. You then switch for as long as you need to return the heap to it's correct state

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

所有交换的成本你日志N 的时间。

如果你不是替换 4 根节点，你还是要通过左分支reheapify结构增加成本来提取根的线性成本节点。如果那一堆看起来像这样

If you instead replaced the root node with 4, you would still have to go through the left branch to reheapify the structure adding cost to the linear cost of extracting the root nodes. What if the heap looked like this

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

该页面我看着形成解决方案

The pages I looked at forming the solution

1）维基百科：二叉堆

2）的Wolfram MathWorld：堆这里的堆是理解为什么它不是一个线性操作特别有用

2) Wolfram MathWorld: heap The heaps here are especially helpful in understanding why it's not a linear operation.

这篇关于打印的排序顺序使用堆属性树（Cormen）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！