证明或反驳：存在一种通用排序算法，如果它是最小堆有序的，它可以在 O(n) 中对长度为 n 的数组进行排序
Prove or disprove: There is a general sorting algorithm which can sort an array of length n in O(n) if it's min-heap-ordered
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).
中进行排序
很确定我的解决方案是错误的，请告诉我你是如何正确解决的，非常抱歉我的英语我尽力了..
我想我解决的是miss，我需要证明min-heap-ordered没有排序的叶子？但是怎么办？
这类问题的通常证明是将一些众所周知的问题归结为你的问题。也就是说，您表明如果可以在线性时间内解决您的问题，那么也可以在线性时间内解决某些问题 X。但众所周知 X 在线性时间内不可解，因此自相矛盾，你的问题也不是。
此类问题 X 的一个很好的例子是排序。众所周知，不可能在 Omega(n log n) 时间内对 N 个元素进行排序（这里的 Omega 是处理下界的正确方法，参见 here）。
现在请注意，如果我们：
- 从 N 个元素创建一个最小堆
- 从最小堆顺序对 N 个元素进行排序
然后我们从头开始有效地对这些元素进行排序。因此，这两个步骤中的任何一个都至少需要 n log n 时间。存在一种算法可以在线性时间内执行第一步（它应该在您的教科书中），为我们提供第二步的 Omega(n log n) 下限，Q.E.D.
这个解决方案完全正确。您可以通过使用假设排序算法生成线性时间一般排序算法来生成正式证明 reductio ad absurdum（减少矛盾）。
对数组 A 进行排序的线性时间算法包括从小于 min(A) 的有序整数序列开始构造堆排序数组，然后添加 A 在末尾。这个新数组的总长度是 O(|A|) —— 对于堆的标准数组表示，你需要下一个更大的 2 元素的幂，最多是 3·|A|。然后，您可以使用线性时间算法对堆有序数组进行排序，以对这个新数组进行排序，最后删除前置序列以按排序顺序生成原始数组。
由于这与众所周知的线性时间一般排序不可能的结果相矛盾，我们可以得出结论，不存在用于对堆有序数组进行排序的线性时间算法。
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.
明天我要参加考试，并且非常害怕证明任务...这是我从较早的考试中找到的，并且很难按预期解决...：/
我想我知道答案，但我的理由不充分。所以我的理由是这个陈述是错误的，因为当数组是最小堆排序时，让我们把它想象成一棵树，那么树的叶子将不会被排序。在 O(n) 中对数组进行排序需要该数组已排序。由于这个原因陈述是错误的..
这里我有一个例子，我制作了我自己的最小堆有序树：
1
/ \
3 2
/ \ \
8 99 7
由此我们创建数组，我们有 1, 3, 2, 8, 99, 7 你看这根本没有排序，而是最小堆排序。无法在 O(n).
很确定我的解决方案是错误的，请告诉我你是如何正确解决的，非常抱歉我的英语我尽力了..
我想我解决的是miss，我需要证明min-heap-ordered没有排序的叶子？但是怎么办？
这类问题的通常证明是将一些众所周知的问题归结为你的问题。也就是说，您表明如果可以在线性时间内解决您的问题，那么也可以在线性时间内解决某些问题 X。但众所周知 X 在线性时间内不可解，因此自相矛盾，你的问题也不是。
此类问题 X 的一个很好的例子是排序。众所周知，不可能在 Omega(n log n) 时间内对 N 个元素进行排序（这里的 Omega 是处理下界的正确方法，参见 here）。
现在请注意，如果我们：
- 从 N 个元素创建一个最小堆
- 从最小堆顺序对 N 个元素进行排序
然后我们从头开始有效地对这些元素进行排序。因此，这两个步骤中的任何一个都至少需要 n log n 时间。存在一种算法可以在线性时间内执行第一步（它应该在您的教科书中），为我们提供第二步的 Omega(n log n) 下限，Q.E.D.
这个解决方案完全正确。您可以通过使用假设排序算法生成线性时间一般排序算法来生成正式证明 reductio ad absurdum（减少矛盾）。
对数组 A 进行排序的线性时间算法包括从小于 min(A) 的有序整数序列开始构造堆排序数组，然后添加 A 在末尾。这个新数组的总长度是 O(|A|) —— 对于堆的标准数组表示，你需要下一个更大的 2 元素的幂，最多是 3·|A|。然后，您可以使用线性时间算法对堆有序数组进行排序，以对这个新数组进行排序，最后删除前置序列以按排序顺序生成原始数组。
由于这与众所周知的线性时间一般排序不可能的结果相矛盾，我们可以得出结论，不存在用于对堆有序数组进行排序的线性时间算法。