Prove or disprove: There is a general sorting algorithm which can sort an array of length
ninO(n)if the array is min-heap-ordered.证明或不证明:有一个通用的排序算法，如果数组是最小的-heap-有序的，那么它可以在O(n)中对长度为n的数组进行排序。
Tomorrow I write exam and very scared from proof task... Here is one I find from older exam and very hard for solve as expected... : /
明天我写考试，很害怕考试……这是我从以前的考试中发现的，很难像预期的那样解决。:/
I think I know answer but my reason isn't good. So my reason is the statement is false because when array is min-heap-ordered, let imagine it as a tree, then the leaves of the tree will not be sorted. And that array is sorted is required for sorting it in O(n). For this reason statement is wrong..
我想我知道答案，但我的理由不太好。我的理由是这个语句是错误的因为当数组是最小的-heap排序的时候，假设它是一个树，那么树的叶子就不会被排序。这个数组在O(n)中排序是必需的。因此，这种说法是错误的。
Here I have example I make my own min-heap-ordered tree:
这里我有一个我自己的minheapo命令树:
1
/ \
3 2
/ \ \
8 99 7
From this we make array, we have 1, 3, 2, 8, 99, 7 You see this is no sorted at all but min-heap-ordered. No possible to sort this in O(n).
从这里我们创建数组，我们有1 3 2 8 99 7，你可以看到这不是有序的，只是有最小的heap。不可能在O(n)中进行排序。
Very sure my solve is wrong pls can you show me how you do it correct and very sorry for my English I try my best..
我的答案肯定是错的，请告诉我你是怎么做的，并为我的英语感到抱歉我已经尽力了。
I think what my solve is miss, I need prove that min-heap-ordered have no sorted leaves? But how?
我想我的答案是漏，我需要证明我的排序没有排序的叶子?但如何?
2 个解决方案
#1
3
This solution is precisely correct. You can produce a formal proof reductio ad absurdum (reduction to a contradiction) by using the hypothetical sorting algorithm to produce a linear-time general sorting algorithm.
这个解决方案是完全正确的。你可以用假设的排序算法产生一个线性时间的一般排序算法，从而产生一个正式的反证法(还原为矛盾)。
The linear-time algorithm to sort the array A consists of constructing a heap-ordered array by starting with an ordered sequence of integers less than min(A), and then adding A at the end. The total length of this new array is O(|A|) -- with the standard array representation of a heap, you need the next larger power of 2 elements, which is at most 3·|A|. You can then use the linear-time algorithm to sort a heap-ordered array to sort this new array, and finally remove the prepended sequence to produce the original array in sorted order.
对数组A进行排序的线性时间算法包括构造一个以小于min(A)的整数的有序序列为开始，然后在末尾添加一个A的哈希有序数组。这个新数组的总长度是O(|A|)——使用堆的标准数组表示，您需要2个元素的下一个更大的幂，最多3·|A|。然后，您可以使用线性时间算法对一堆有序数组进行排序，以对这个新数组进行排序，最后删除预编序列，以按排序顺序生成原始数组。
Since that contradicts the well-known result that linear-time general sorting is impossible, we can conclude that there is no linear-time algorithm for sorting a heap-ordered array.
由于这与线性时间一般排序是不可能的这一众所周知的结果相矛盾，我们可以得出这样的结论:没有线性时间算法来对一堆有序数组进行排序。
#2
1
The usual proof for this kind of problems is reducing some well-known problem to yours. That is, you show that if it possible to solve your problem in linear time then it is also possible to solve some problem X in linear time. But it is known that X is not solvable in linear time, thus by contradiction your problem is not as well.
对于这类问题，通常的证明是把一些众所周知的问题降低到你的问题上。也就是说，如果有可能在线性时间内解决问题那么也有可能在线性时间内解决某个问题X。但是我们知道X在线性时间内是不可解的，因此矛盾的是你的问题也不是那么好。
An excellent example of such problem X is sorting. It is well-known that it is impossible to sort N elements in Omega(n log n) time (Omega here is a proper way to deal with lower bounds, see here).
这类问题的一个很好的例子是排序。众所周知，在(N log N)时间内对N个元素进行排序是不可能的(这里有一个处理下界的合适方法，见这里)。
Now note that if we:
请注意，如果我们:
- make a min-heap from N elements
- 从N个元素组成一个小堆
- sort N elements from min-heap order
- 按照最小堆的顺序对N个元素进行排序
then we effectively sort these elements from scratch. Thus either of these two steps takes at least n log n time. There exists an algorithm to perform the first step in linear time (it should likely be in your textbook), giving us the Omega(n log n) lower bound for the second step, Q.E.D.
然后我们有效地从头对这些元素进行排序。因此，这两个步骤至少需要n log n的时间。有一种算法可以在线性时间内执行第一步(应该在课本中)，给出了第二步的下界(n log n) Q.E.D.
#1
3
This solution is precisely correct. You can produce a formal proof reductio ad absurdum (reduction to a contradiction) by using the hypothetical sorting algorithm to produce a linear-time general sorting algorithm.
这个解决方案是完全正确的。你可以用假设的排序算法产生一个线性时间的一般排序算法，从而产生一个正式的反证法(还原为矛盾)。
The linear-time algorithm to sort the array A consists of constructing a heap-ordered array by starting with an ordered sequence of integers less than min(A), and then adding A at the end. The total length of this new array is O(|A|) -- with the standard array representation of a heap, you need the next larger power of 2 elements, which is at most 3·|A|. You can then use the linear-time algorithm to sort a heap-ordered array to sort this new array, and finally remove the prepended sequence to produce the original array in sorted order.
对数组A进行排序的线性时间算法包括构造一个以小于min(A)的整数的有序序列为开始，然后在末尾添加一个A的哈希有序数组。这个新数组的总长度是O(|A|)——使用堆的标准数组表示，您需要2个元素的下一个更大的幂，最多3·|A|。然后，您可以使用线性时间算法对一堆有序数组进行排序，以对这个新数组进行排序，最后删除预编序列，以按排序顺序生成原始数组。
Since that contradicts the well-known result that linear-time general sorting is impossible, we can conclude that there is no linear-time algorithm for sorting a heap-ordered array.
由于这与线性时间一般排序是不可能的这一众所周知的结果相矛盾，我们可以得出这样的结论:没有线性时间算法来对一堆有序数组进行排序。
#2
1
The usual proof for this kind of problems is reducing some well-known problem to yours. That is, you show that if it possible to solve your problem in linear time then it is also possible to solve some problem X in linear time. But it is known that X is not solvable in linear time, thus by contradiction your problem is not as well.
对于这类问题，通常的证明是把一些众所周知的问题降低到你的问题上。也就是说，如果有可能在线性时间内解决问题那么也有可能在线性时间内解决某个问题X。但是我们知道X在线性时间内是不可解的，因此矛盾的是你的问题也不是那么好。
An excellent example of such problem X is sorting. It is well-known that it is impossible to sort N elements in Omega(n log n) time (Omega here is a proper way to deal with lower bounds, see here).
这类问题的一个很好的例子是排序。众所周知，在(N log N)时间内对N个元素进行排序是不可能的(这里有一个处理下界的合适方法，见这里)。
Now note that if we:
请注意，如果我们:
- make a min-heap from N elements
- 从N个元素组成一个小堆
- sort N elements from min-heap order
- 按照最小堆的顺序对N个元素进行排序
then we effectively sort these elements from scratch. Thus either of these two steps takes at least n log n time. There exists an algorithm to perform the first step in linear time (it should likely be in your textbook), giving us the Omega(n log n) lower bound for the second step, Q.E.D.
然后我们有效地从头对这些元素进行排序。因此，这两个步骤至少需要n log n的时间。有一种算法可以在线性时间内执行第一步(应该在课本中)，给出了第二步的下界(n log n) Q.E.D.