arrays - 证明或反驳 : There is a general sorting algorithm which can sort an array of length n in O(n) if it's min-heap-ordered

Question

Prove or disprove: There is a general sorting algorithm which can sort an array of length n in O(n) if the array is min-heap-ordered.

明天我要写考试，非常害怕证明任务...这是我从旧考试中找到的，很难按预期解决...:/

我想我知道答案，但我的理由不充分。所以我的理由是这个陈述是错误的，因为当数组是最小堆排序时，让我们把它想象成一棵树，那么树的叶子将不会被排序。并且需要在 O(n) 中对数组进行排序。由于这个原因，陈述是错误的..

这里我有一个例子，我制作了我自己的最小堆有序树:

       1
      / \
     3   2
    / \   \
   8   99  7

由此我们创建数组，我们有 1, 3, 2, 8, 99, 7 你看这根本没有排序，而是最小堆排序。无法在 O(n) 中对其进行排序。

---

非常确定我的解决方案是错误的，请告诉我你是如何正确解决问题的，非常抱歉我的英语我尽力了..

我想我的解决方法是小姐，我需要证明最小堆有序没有排序的叶子？但是如何呢？

Answer 1

这个解决方案是完全正确的。您可以通过使用假设排序算法生成线性时间一般排序算法来生成正式证明reductio ad absurdum(减少矛盾)。

对数组 A 进行排序的线性时间算法包括从小于 min(A) 的有序整数序列开始构建堆有序数组，然后在末尾添加 A。这个新数组的总长度是 O(|A|) —— 对于堆的标准数组表示，您需要下一个更大的 2 元素的幂，最多为 3 ·|A|。然后，您可以使用线性时间算法对堆有序数组进行排序，以对这个新数组进行排序，最后删除前置序列以生成按排序顺序排列的原始数组。

由于这与众所周知的线性时间一般排序不可能的结果相矛盾，我们可以得出结论，不存在用于对堆有序数组进行排序的线性时间算法。