sun*_*oon 17 c algorithm heap binary-tree
我们给出了一个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是阵列的输入大小.因此,我们只是从一端到另一端遍历数组,并以最后一行(即数组的后半部分)正确的方式交换不均匀的位置.这可以就地完成.然后,我们对数组的前半部分进行排序(使用例如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,以便整个内容完全就地工作.
对不起,我不能进一步详细说明,但我认为你可以得到这个想法.