将最大堆转换为二叉搜索树

Question

我们得到一个包含 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 

现在当看成一棵二叉树时，这些元素满足堆性质，一个节点大于它的两个 child :

A[i] > A[2i] 和 A[i] > A[2i+1]

是否有相当快的就地算法来随机排列数组的元素，以便生成的二叉树(如上所述)是一棵二叉搜索树？

回想一下，在二叉搜索树中，一个节点大于其所有左后代，且小于其所有右后代。

例如，上述数组的重新洗牌将是

[4 2 6 1 3 5 7]

对应二叉搜索树

       4
    /    \
   2       6
  /  \    / \
 1    3   5  7 

Answer 1

首先我们注意到我们可以——不失一般性——假设我们的二叉树中有元素 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 等就地排序算法，这样整个事情才能完全就地工作。

很抱歉我不能进一步详细说明，但我想你能明白这个想法。