我们得到一个 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
现在，当被视为二叉树时，这些元素满足堆属性，一个节点大于它的两个子节点：
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,...。所以，从现在开始，我们假设我们有这些数字。
然后，我的尝试将是一些将排序数组（即1 2 3 4 5）转换为表示排序二叉树的数组的函数。
在具有元素的排序二叉树中，(2^m)-1我们始终认为树的“底部”由所有奇数组成，例如m=3：
4
2 6
1 3 5 7
这意味着，在相应的数组中，最后一个数字都是奇数：
4 2 6 1 3 5 7
-------
^
uneven numbers!
2^(m-1)所以我们可以通过确保对应数组的最后一个数字都是奇数来构造二叉树的最后“行” 。因此，我们需要为最后一行做的就是构造一个函数，将索引不均匀的位置的所有元素移动到最后一行。
所以现在让我们假设我们有一个例程——给定一个排序数组作为输入——正确地建立最后一行。
然后我们可以调用整个数组的例程来构造最后一行，而所有其他元素保持排序。当我们在数组上应用这个例程时1 2 3 4 5 6 7，我们有以下情况：
2 4 6 1 3 5 7
-------
^
correct!
在第一轮之后，我们将例程应用于2 4 6构建二叉树的倒数第二“行”的剩余子数组（即 ），同时保持剩余元素不变，因此我们得到以下结果：
now correct as well!
v
---
4 2 6 1 3 5 7
-------
^
correct from run before
所以我们所要做的就是构造一个函数来正确安装最后一行（即数组的后半部分）！
这可以在数组的输入大小在O(n log n)哪里完成。n因此，我们只是从头到尾遍历数组，交换不均匀的位置，使最后一行（即数组的后半部分）正确。这可以就地完成。之后，我们对数组的前半部分进行排序（例如使用堆排序）。所以这个子程序的整个运行时间是O(n log n).
所以一个大小数组的运行时间n是：
O(n log n) + O(n/2 log n/2) + O(n/4 log n/4) + ...这与 相同O(n log n)。请注意，我们必须使用诸如 Heapsort 之类的就地排序算法，以便整个工作完全就地。
很抱歉，我无法进一步详细说明，但我认为您可以理解。
让 n = 2 m - 1。在线性时间内，我们既可以创建一个最大堆，也可以按排序顺序提取二叉搜索树的元素，所以我们希望的最好结果（假设基于比较的算法）是 O( n log n) 时间和 O(1) 空间。这是一个这样的算法。
对于 j = n 到 1，从 j 元素最大堆中弹出最大元素并将其存储在（新腾出的）位置 j。这对数组进行排序。
使用分而治之的策略将排序后的数组转换为二叉搜索树。（天真这是 Omega(log n) 空间，但我相信我们可以将堆栈压缩为 O(1) log(n) 位字。）
一个。树化小于根的元素。
湾。树化大于根的元素。
C。通过将小于根的叶子旋转到适当的位置（= 三个反向）来合并树，以便留下一半大小的子问题（O（n））。
(08 04 12 02 06 10 14 01 03 05 07 09 11 13 15)16(24 20 28 18 22 26 30 17 19 21 23 25 27 29 31)
(08 04 12 02 06 10 14)16(24 20 28 18 22 26 30)01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31
(08 04 12)16(24 20 28)02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31
(08)16(24)04 12 20 28 02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31
16 08 24 04 12 20 28 02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31
只是一些基本的想法：
条件 1 没有问题 - 堆也是二叉树。条件 2 存在问题，但建议采用自下而上的方法。条件 3 也不满足。
自下而上意味着： - 我们从所有叶子开始 - 这没有问题，它们是二叉搜索树。- 现在我们继续递归遍历每个级别的父母直到根。- 如果左孩子大于右孩子，则交换子树。- 用 2 个孩子中较大的值交换根（它是右孩子） - 这可能还不够 - 您可能需要继续纠正右子树，直到它再次成为二叉搜索树。
这应该有效。但是仍然 - 删除顶部元素并将其插入到自平衡树中将是更快/更好的方法并且更容易实现（例如，在 c++ 中使用标准组件，如 std::map ）。
另一个想法：对于二叉搜索树来说，左-根-右遍历树获得排序值的属性。这可以反过来进行。从堆中获取排序的值也应该很容易。只需尝试将其结合起来 - 从堆中读取并直接从排序值中写入树。我认为这可以在 O(n) 中完成 - 但我不确定它是否可以就地完成 - 我猜不是。