我们得到一个包含 2m - 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
现在当看成一棵二叉树时,这些元素满足堆性质,一个节点大于它的两个 child :
A[i] > A[2i] 和 A[i] > A[2i+1]
是否有相当快的就地算法来随机排列数组的元素,以便生成的二叉树(如上所述)是一棵二叉搜索树?
回想一下,在二叉搜索树中,一个节点大于其所有左后代,且小于其所有右后代。
例如,上述数组的重新洗牌将是
[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)
数都是奇数来构造二叉树的最后“行”。因此,对于最后一行,我们需要做的就是构造一个函数,将索引不均匀的位置上的所有元素移动到最后一行。
现在让我们假设我们有一个例程——给定一个排序数组作为输入——正确地建立最后一行。
然后我们可以调用整个数组的例程来构造最后一行,而所有其他元素保持排序。当我们将此例程应用于数组 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 等就地排序算法,这样整个事情才能完全就地工作。
很抱歉我不能进一步详细说明,但我想你能明白这个想法。
关于将最大堆转换为二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4966014/