将最大堆转换为二叉搜索树
我们得到一个 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
现在，当看成二叉树时，这些元素满足堆属性，一个节点大于它的两个子节点：
A[i] > 5 2 3 1] 是树。 A[2i]和A[i]＞ A[2i+1]
是否有相当快的就地算法来打乱数组的元素，以便生成的二叉树（如上所述）是二叉搜索树？
回想一下，在二叉搜索树中，一个节点大于其所有左后代，并小于其所有右后代。
例如，上述数组的重新洗牌将是
[4 2 6 1 3 5 7]
，它对应于二叉搜索树
4
/ \
2 6
/ \ / \
1 3 5 7
We are given an array of 2m - 1 distinct, comparable elements, indexed starting from 1.
We can view the array as a complete binary tree:
Node is placed at index i.
Left child is placed at 2i.
Right child is placed at 2i+1.
For instance, the array
[7 6 4 5 2 3 1]
is the tree
7
/ \
6 4
/ \ / \
5 2 3 1
Now when viewed as a binary tree, these elements satisfy the heap property, a node is greater than both its children:
A[i] > A[2i] and A[i] > A[2i+1]
Are there reasonably fast, in-place algorithm to shuffle the elements of the array around so that the resulting binary tree (as described above) is a binary search tree?
Recall that in a binary search tree, a node is greater than all its left descendants, and less than all its right descendants.
For instance the reshuffle of the above array would be
[4 2 6 1 3 5 7]
which corresponds to the binary search tree
4
/ \
2 6
/ \ / \
1 3 5 7
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
首先我们注意到，在不失一般性的情况下，我们可以假设我们的二叉树中有元素 1,2,3,...
2^m-1。所以，从现在开始，我们假设我们有这些数字。然后，我尝试使用一些函数将排序数组（即
1 2 3 4 5）转换为表示排序二叉树的数组。在具有
(2^m)-1元素的排序二叉树中，我们始终认为树的“底部”由所有奇数组成，例如m=3>：这意味着，在相应的数组中，最后的数字都是奇数：
因此我们可以通过确保最后的
2^(m-1) 来构造二叉树的最后“行”对应数组中的数字都是奇数。因此，我们对最后一行需要做的就是构造一个函数，将索引不均匀位置上的所有元素移动到最后一行。现在让我们假设我们有一个例程——给定一个排序数组作为输入——正确地建立最后一行。
然后我们可以调用整个数组的例程来构造最后一行，同时所有其他元素保持排序。当我们将这个例程应用于数组
1 2 3 4 5 6 7时，我们会遇到以下情况：第一轮之后，我们将例程应用于剩余的子数组（即
2 4 6），它构造了二叉树的倒数第二“行”，而我们保留其余元素不变，因此我们得到以下结果：因此，我们所要做的就是构造一个安装最后一行的函数（即数组的后半部分）正确！
这可以在
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)相同。请注意，我们必须使用就地排序算法（例如堆排序），以便整个工作完全就地进行。很抱歉我无法进一步阐述，但我想你可以明白这个想法。
First we note that we can -- without loss of generality -- assume that we have the elements 1,2,3,...
2^m-1in our binary tree. So, from now on, we assume that we have these numbers.Then, my attempt would be some function to convert a sorted array (i.e.
1 2 3 4 5) into an array representing a sorted binary tree.In a sorted binary tree with
(2^m)-1elements we have always that the "bottom" of the tree consists of all the uneven numbers, e.g. form=3:This means, in the corresponding array, we have that the last numbers are all the uneven numbers:
So we can construct the last "row" of the binary tree by ensuring that the last
2^(m-1)numbers in the corresponding array are all the uneven numbers. So all we need to do for the last row is to construct a function that moves all elements at positions with uneven indices to the last row.So let us for now assume that we have a routine that -- given a sorted array as input -- establishes the last row correctly.
Then we can call the routine for the whole array to construct the last row while all other elements stay sorted. When we apply this routine on the array
1 2 3 4 5 6 7, we have the following situation:After the first round, we apply the routine for the remaining subarray (namely
2 4 6) which constructs the second last "row" of our binary tree, while we leave the remaining elements unchanged, so we get the following:So all we have to do is to construct a function that installs the last row (i.e. the second half of the array) correctly!
This can be done in
O(n log n)wherenis the input size of the array. Therefore, we just traverse the array from end to the beginning and exchange the uneven positions in such a way that the last row (i.e. the latter half of the array) is correct. This can be done in-place. Afterwards, we sort the first half of the array (using e.g. heapsort). So the whole runtime of this subroutine isO(n log n).So the runtime for an array of size
nin total is:O(n log n) + O(n/2 log n/2) + O(n/4 log n/4) + ...which is the same asO(n log n). Note that we have to use a in-place sorting algorithm such as Heapsort so that this whole stuff works completely in-place.I'm sorry that I can't elaborate it further, but I think you can get the idea.
让 n = 2m - 1。在线性时间内，我们既可以创建一个最大堆，又可以按排序顺序提取二叉搜索树的元素，因此我们可以期望的最好结果（假设比较基于算法）的时间复杂度为 O(n log n)，空间复杂度为 O(1)。这是这样一个算法。
当 j = n 降至 1 时，从 j 元素最大堆中弹出最大元素并将其存储在（新腾出的）位置 j 处。这会对数组进行排序。
使用分治策略将排序数组转换为二叉搜索树。 （天真地说，这是 Omega(log n) 空间，但我相信我们可以将堆栈压缩为 O(1) log(n) 位字。）
a.将小于根的元素树化。
b.将大于根的元素树化。
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 31Let n = 2m - 1. In linear time, we can both make a max-heap and extract the elements of a binary search tree in sorted order, so the best we can hope for (assuming comparison-based algorithms) is O(n log n) time and O(1) space. Here is such an algorithm.
For j = n down to 1, pop the max element from the j-element max-heap and store it at (newly vacated) location j. This sorts the array.
Convert the sorted array to a binary search tree with a divide and conquer strategy. (Naively this is Omega(log n) space, but I believe we can compress the stack to O(1) log(n)-bit words.)
a. Treeify the elements less than the root.
b. Treeify the elements greater than the root.
c. Merge the trees by rotating the leaves less than the root into position (= three reverses) so as to leave a subproblem of half the size (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一些基本想法：
条件 1 不是问题 - 堆也是二叉树。
条件 2 存在问题，但建议采用自下而上的方法。
条件3也不满足。
自下而上的意思是：
- 我们从所有叶子开始 - 这是没有问题的，它们是二叉搜索树。
- 现在我们继续递归遍历每个级别的父项直至根。
- 如果左子树大于右子树，则交换子树。
- 将根与 2 个子节点中较大的值交换（它是右子节点）
- 这可能还不够 - 您可能需要继续纠正右子树，直到它再次成为二叉搜索树。
这应该有效。但仍然 - 删除顶部元素并将其插入到自平衡树中将是更快/更好的方法，并且更容易实现（例如，使用标准组件，如 c++ 中的 std::map）。
另一个想法：二叉搜索树具有这样的属性：左根右遍历树可以获得排序值。这可以反过来进行。从堆中获取值排序也应该很容易。只需尝试将其结合起来 - 从堆读取并直接从排序值写入树。我认为这可以在 O(n) 内完成 - 但我不确定它是否可以就地完成 - 我想不能。
Just some basic ideas:
Condition 1 is not problem - the heap is a binary tree as well.
Condition 2 is problematic but suggests a bottom up approach.
Condition 3 is not satisfied as well.
Bottom up means:
- We start with all leaves - this is unproblematic, they are binary search trees.
- Now we continue with a recursive walk through each level of parents up to the root.
- Swap the subtrees if the left child is larger than the right child.
- Swap the root with the larger value of the 2 children (it's the right child)
- This might not be enough - you might need to continue to correct the right subtree until it is a binary search tree again.
This should work. But still - removing the top element and inserting it into a self balancing tree will be the faster/better approach and a lot easier to implement (e.g. using standard components like std::map in c++).
Another idea: for binary search trees holds the property that a left-root-right walk through the tree obtains the sorted values. This could be done reverse. Getting the values sorted from the heap should be easy as well. Just try to combine this - reading from the heap and writing the tree directly from the sorted values. This can be done in O(n) I think - but I'm not sure wether it can be done in place or not - I guess not.