使用堆属性按排序顺序打印树 (Cormen)
我正在刷新算法理论（来自 Cormen）。
二进制尝试一章中有一个练习，要求：
min-heap属性可以用来打印n个节点的键吗 在 O(n) 时间内排序树？展示如何做，或解释为什么不做。
我认为是的，这是可能的。
在最小堆中，节点中的元素小于其两个子节点。
因此，堆的根始终是所有 n 个元素中较小的元素，并且根的左孩子比左子树中的所有元素小，根的右孩子比左子树中的所有元素小。右子树等。
因此，如果继续提取根，打印它，然后用其较小的子树更新根，我们保留最小堆属性并按排序顺序打印。 （我正在考虑一个不基于数组的最小堆）。
因此，这可以在 O(n) 时间内完成，因为要更新根，我们只需比较 2 个子级并将根的指针更新为 2 中较小的一个。
但我在解决方案中检查了这里：
Cormen 补充解决方案
1）它讨论了最大堆 2）它说它不能在 O(n) 时间内完成：
在堆中，节点的键是其子节点的键。在二进制中 搜索树，节点的键是其左孩子的键，但其右孩子的键 孩子的钥匙。堆属性，与二叉树不同 属性，无助于按排序顺序打印节点，因为它 不知道节点的哪个子树包含要打印的元素 在该节点之前。堆中，小于节点的最大元素 可以在任一子树中。请注意，如果堆属性可以是 用于在 O(n) 时间内按排序顺序打印键，我们将得到一个 用于排序的 O(n) 时间算法，因为构建堆只需要 准时。但我们知道（第 8 章）比较排序必须采用 (n lg n) 时间。
从我的角度来看，我可以理解使用最大堆，不可能在 O(n) 中打印它们。
但是，根据我解释的推理，是否可以使用 min-heap 属性来做到这一点？
另外为什么解决方案忽略最小堆。是拼写错误还是错误？
我在这里误解了什么吗？
I am refreshing on algorithm theory (from Cormen).
There is an exercise in the chapter for binary tries that asks:
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.
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.
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).
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.
But I checked here in the solution:
Cormen Supplement Solutions
And 1)it talks about max-heaps 2) it says it can not be done in O(n) time:
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.
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?
Am I misundertanding something here?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
首先，讨论中省略最小堆可能不是一个错字，我们讨论的是最小堆还是最大堆并不重要（比较器只是相反）。
仅提取根然后用其两个子树中较小的一个替换的问题是，不能保证左子树小于右子树中的所有节点（反之亦然）。考虑以下堆
在打印
1后，您必须重新堆化，也就是说您提取1并将其替换为最后一行中的最后一个元素，在本例中为7.。然后，只要您需要将堆返回到正确的状态，您就可以进行切换，所有这些交换都会花费您
log n时间。如果您用
4替换根节点，您仍然需要通过左分支来重新堆放结构，从而增加提取根节点的线性成本。如果堆看起来像这样我查看形成解决方案的页面
1) 维基百科：二进制堆
2) Wolfram MathWorld：堆 这里的堆对于理解为什么它特别有帮助不是线性运算。
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
After printing
1you have to reheapify which is to say you extract1and replace it with the last element in the last row, in this case7. You then switch for as long as you need to return the heap to it's correct stateall of that swapping costs you
log ntime.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 thisThe pages I looked at forming the solution
1) Wikipedia: binary heap
2) Wolfram MathWorld: heap The heaps here are especially helpful in understanding why it's not a linear operation.
考虑最小堆的数组表示。你在根部有最小值。提取根并将其替换为最后一个数组元素，即最低的、不完整的叶子“行”中的最后一个叶子。执行 MIN-HEAPIFY 操作（与 CLRS MAX-HEAPIFY 相同，但比较相反）。这需要 O(log n)，结果是根中倒数第二小的元素。重复直到堆为空。这给出了一个排序序列。
因此，算法的复杂度
为 O(n*log n)，
这是预期的，否则，我们将获得复杂度小于 O(nlogn) 的基于比较的排序，而这是不可能的。
Consider an array representation of the min-heap. You have the minimum at the root. Extract the root and replace it with the last array element, i.e. with the last leaf in the lowest, incomplete "row" of leaves. Perform the MIN-HEAPIFY operation (obv. same as CLRS MAX-HEAPIFY, but with reversed comparison). This takes O(log n) and result is the second least element at the root. Repeat until the heap is empty. This gives a sorted sequence.
The complexity of the algorithm is therefore
i.e. O(n*log n)
which is to be expected or otherwise, we would have obtained a comparison based sort with complexity less than O(nlogn) and this is impossible.
我想您的想法基本上是，堆（考虑最小堆）以最小的元素作为其根。现在对于第二小的元素，左子树和右子树都具有最小堆属性，因此我们可以简单地比较左右子树来找到第二小的元素。同样可以继续......所以它的 O(n) ？
您忽略的一件事是，随着每个级别的增加，要比较的元素数量也在增加......
最小 - 0 比较（根是最小的）
对于第二小的 - 1 比较（左树的根或右树的根）
假设左树根节点小于右树根节点。
对于第三小的 - 2 比较。 （右树的根或左子树的两个子树之一）。
您在计算渐近时间复杂度时忽略了这个比较部分。
I guess what you are thinking is basically, that a heap (considering a min heap), has the smallest element as its root. Now for the second smallest element, both the left and right subtree have min heap property, so we can simply compare the left and right child to find the second smallest element. And same can be continued.... so its O(n) ?
One thing that you are ignoring is that with each level the number of elements to be compared are also increasing...
for the smallest - 0 comparison (root is the smallest)
for the second smallest - 1 comparison (either root of left tree or root of right tree)
lets say left tree root is smaller than right tree root node.
for third smallest - 2 comparison. ( either root of right tree or either of two children of left subtree).
You are ignoring this comparison part for your calculation of asymptotic time complexity.