我们给了一个2 m -1个不同的可比较元素的数组，索引从1开始。
我们可以将数组视为完整的二叉树：
Node is placed at index i. Left child is placed at 2i. Right child is placed at 2i+1.
例如，数组
[7 6 4 5 2 3 1]
是树吗
7 / \ 6 4 / \ / \ 5 2 3 1
现在，当将它们视为二叉树时，这些元素满足了heap属性，一个节点大于其两个子节点：
A[i] > A[2i] and A[i] > A[2i+1]
是否有相当快速的就地算法来对数组的元素进行混洗，以使生成的二叉树（如上所述）成为二叉 搜索 树？
回想一下，在二叉搜索树中，节点大于其所有左后代，并且小于其所有右后代。
例如，上述数组的改组将是
[4 2 6 1 3 5 7]
对应于二叉搜索树
4 / \ 2 6 / \ / \ 1 3 5 7
首先，我们注意到我们可以-在不失一般性的前提下-假设我们2^m-1在二叉树中有1,2,3，…元素。因此，从现在开始，我们假设我们拥有这些数字。
2^m-1
然后，我将尝试一些将排序后的数组（即1 2 3 4 5）转换为表示排序后的二叉树的数组的函数。
1 2 3 4 5
在带有(2^m)-1元素的分类二叉树中，我们总是认为树的“底部”由所有不均匀数组成，例如m=3：
(2^m)-1
m=3
4 2 6 1 3 5 7
这意味着，在相应的数组中，我们有最后的数字都是不均匀数字：
4 2 6 1 3 5 7 ------- ^ uneven numbers!
因此，我们可以通过确保2^(m-1)对应数组中的最后一个数字都是不均匀数来构造二叉树的最后一个“行” 。因此，对于最后一行，我们要做的就是构造一个函数，以将索引不均匀的位置处的所有元素移动到最后一行。
2^(m-1)
因此，现在让我们假设我们有一个例程-给定排序数组作为输入-正确建立最后一行。
然后，我们可以调用整个数组的例程以构造最后一行，而所有其他元素保持排序。在数组上应用此例程时1 2 3 4 5 6 7，会出现以下情况：
1 2 3 4 5 6 7
2 4 6 1 3 5 7 ------- ^ correct!
在第一轮之后，我们对剩下的子数组（即2 4 6）应用例程，该子数组构造了我们的二叉树的倒数第二个“行”，而剩下的元素保持不变，因此得到以下结果：
2 4 6
now correct as well! v --- 4 2 6 1 3 5 7 ------- ^ correct from run before
因此，我们要做的就是构造一个可以正确安装最后一行（即数组的后半部分）的函数！
可以在O(n log n)哪里n输入数组的大小。因此，我们只是从头到尾遍历数组，并交换不平坦位置，以使最后一行（即数组的后半部分）正确。这可以就地完成。然后，我们对数组的前半部分进行排序（例如使用heapsort）。因此，此子例程的整个运行时为O(n log n)。
O(n log n)
n
因此n，总计大小为数组的运行时为：
O(n log n) + O(n/2 log n/2) + O(n/4 log n/4) + ...与相同O(n log n)。请注意，我们必须使用就地排序算法（例如Heapsort），以便整个工作完全就地进行。
O(n log n) + O(n/2 log n/2) + O(n/4 log n/4) + ...
对不起，我无法进一步阐述，但我想您可以理解。
