将最大堆转换为二叉搜索树
我们给出了一个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]
是否存在相当快速的就地算法来重新排列数组的元素，以便生成的二叉树（如上所述）是二叉搜索树？
回想一下，在二叉搜索树中，节点大于其所有左后代，并且少于其所有右后代。
例如，上述arrays的重新洗牌将是
[4 2 6 1 3 5 7]
它对应于二叉搜索树
4 / \ 2 6 / \ / \ 1 3 5 7
首先我们注意到，我们可以 – 不失一般性 – 假设我们的二叉树中有元素1,2,3，… 2^m-1 。 所以，从现在开始，我们假设我们有这些数字。
然后，我的尝试将是一个函数将已排序的数组（即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)数字都是不均匀数字来构造二叉树的最后一行。 因此，我们需要为最后一行做的就是构造一个函数，将具有不均匀索引的位置处的所有元素移动到最后一行。
因此，现在让我们假设我们有一个例程 – 给定一个排序数组作为输入 – 正确建立最后一行。
然后我们可以调用整个数组的例程来构造最后一行，而所有其他元素都保持排序。 当我们在arrays1 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是数组的输入大小。 因此，我们只是从一端到另一端遍历数组，并以最后一行（即数组的后半部分）正确的方式交换不均匀的位置。 这可以就地完成。 然后，我们对数组的前半部分进行排序（使用例如heapsort）。 所以这个子程序的整个运行时间是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元素max-heap中弹出max元素并将其存储在（新腾出的）位置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 3116 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
只是一些基本的想法：
- 二叉搜索树是二叉树。
- root的两个子节点都是nil或者它们自己是二元搜索树
- 这些值满足以下条件：left child
条件1不是问题 – 堆也是二叉树。 条件2存在问题，但建议采用自下而上的方法。 条件3也不满足。
自下而上意味着： – 我们从所有叶子开始 – 这是没有问题的，它们是二叉搜索树。 – 现在我们继续通过递归遍历每个级别的父级到根。 – 如果左孩子比右孩子大，则交换子树。 – 用2个孩子的较大值（它是正确的孩子）交换根 – 这可能还不够 – 你可能需要继续纠正正确的子树，直到它再次成为二叉搜索树。
这应该工作。 但仍然 – 删除顶部元素并将其插入自平衡树将是更快/更好的方法，并且更容易实现（例如使用标准组件，如c ++中的std :: map）。
另一个想法是：对于二叉搜索树，保持左右根遍历树的属性获得排序值。 这可以反过来做。 获取从堆中排序的值也应该很容易。 只是尝试将它结合起来 – 从堆中读取并直接从排序值中写入树。 这可以在O（n）中完成，我认为 – 但我不确定它是否可以在适当的地方完成 – 我猜不是。
逐个选择原始数组的数组项，然后将它们添加到二进制搜索树中，您可以保持平衡，同时始终确保根位于树的正中间。 例如，通过跟踪根的左侧和右侧的节点数量。