Printing a tree in sorted order using heap properties (Cormen)

Question

I am updating on the theory of algorithms (from Cormen).
There is an exercise for binary attempts in the chapter that asks:

Is it possible to use the min-heap property to print 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 a mini-heap, an element in a node is smaller than its children.
Thus, the heap root is always the smallest element of all n elements, and the left child root is less than all elements in the left subtree, and the right child root is smaller than all elements in the right subtree, etc.

So, if we want to extract the root, print it, and then update the root with fewer children, we will save the min-heap property and print it in sorted order. (I am thinking of a minimal heap that is not array based).

So, this can be done in O (n) time, because to update the root we just compare 2 children and update the root pointer with the smaller of 2.

But I checked here in the solution:
Cormen Supplement Solutions

And 1) he talks about max-heaps 2) he says that this cannot be done in O (n) time:

On the heap, the node s key is both its child keys. In the binary search tree, the key node s is its left child key, but its right child key. The heap property, unlike the binary sea tree property, does not help print nodes in sorted order, because it does not indicate which subtree the node contains the element to print before that node. On the heap, the largest element is smaller than node can be in any subtree. Note that if the heap property can be used to print keys in sorting order in O (n) time, we would have an O (n) -time sorting algorithm, since building a heap takes only On Time. But we know (chapter 8) that sorting should (n lg n).

From my point of view, I can understand that using max heaps it is not possible to print them in O (n).
But is it not possible to do this using the min-heap property for the explanation I explained?
Also why the solution ignores the minimal heap. Is it a typo or a mistake?

Am I misunderstanding something?

Answer 1

Firstly, the omission of the minimum heap in the discussion is probably not a typo, in fact it does not matter whether we are talking about the heap of minutes or the maximum heap (the comparator is simply turned upside down).

The only problem is taking the root, and then replacing it with the smaller of its two children, is that the left child is not guaranteed to be less than all the nodes in the right subtree (and vice versa). Consider the following bunch

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

After printing 1 you will need to update, which means that you extract 1 and replace it with the last element of the last line, in this case 7 . Then you switch until you need to return the heap to the 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 

all this change changes the time log n .

If you replace 4 root directory instead of node root, you still have to go through the left branch to restore the cost of adding the structure to the linear cost of extracting root nodes. What if the heap looked like this:

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

Pages on which I looked at forming a solution

1) Wikipedia: binary heap

2) Wolfram MathWorld: heap Heaps here are especially useful in understanding why this is not a linear operation.

Answer 2

Consider a representation of an array of mini-heaps. You have a minimum in the bud. Extract the root and replace it with the last element of the array, i.e. The last sheet in the bottom, incomplete "row" of leaves. Perform the MIN-HEAPIFY operation (similar to CLRS MAX-HEAPIFY, but with the opposite comparison). This takes O (log n), and the result is the second smallest element in the root. Repeat until the heap is empty. This gives an ordered sequence.

Therefore, the complexity of the algorithm

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

i.e. O (n * log n)

which is to be expected one way or another, we would get a sorting based on comparison with complexity less than O (nlogn), and this is impossible.

Answer 3

I assume that you think, basically, that a bunch (given a bunch of minutes) has the smallest element as its root. Now for the second smallest element, the left and right subtree have the min heap property, so we can simply compare the left and right child elements to find the second smallest element. And the same thing can be continued ... so what's its O (n)? One thing that you ignore is that with each level the number of elements to be compared also increases ... for the smallest - 0 comparisons (the smallest root) for the second smallest - 1 comparison (either the root from the left tree, or root of the right tree) allows us to say that the left root of the tree is smaller than the right root of the tree node. for the third smallest - 2 comparisons. (either the root of the right tree, or either of the two children of the left subtree). You ignore this comparative part to calculate the asymptotic time complexity.