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

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 

现在，将这些元素视为二叉树时，它们满足堆属性，即一个节点大于其两个子节点： A[i] > A[2i] and A[i] > A[2i+1] 是否有一种合理快速、原地算法来重新排列数组的元素，使得所得到的二叉树（如上所述）成为二叉搜索树？

请记住，在二叉搜索树中，一个节点大于其左侧所有后代，小于其右侧所有后代。

例如，上述数组的重排结果是 [4 2 6 1 3 5 7] 对应于二叉搜索树。

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

- sunmoon

---

我认为这个问题很有趣。我已经进行了编辑，并给出了我觉得最合理的解释。（正如R..所说，如果你知道相关术语，这个问题确实是有意义的）。 - Aryabhatta

对于你来说，“原地”是什么意思？是非常严格的O(1)，还是实际定义的O(log n)？ - ltjax

@ltjax：在RAM模型中，O(logn)或者O(1)的时间复杂度。 - Aryabhatta

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)相同。请注意，我们必须使用原地排序算法（如堆排序），以便整个过程完全原地完成。

很抱歉我无法进一步阐述，但我认为你可以理解这个概念。

- phimuemue

---

我从未见过的有趣观察。 - sunmoon

Answer 2

让 n = 2^m - 1。在线性时间内，我们可以同时创建一个最大堆和按排序顺序提取二叉搜索树的元素，因此我们所能希望的最好情况（假设基于比较的算法）是 O(n log n) 的时间和 O(1) 的空间。以下是这样一种算法。

1. 对于 j = n 到 1，从 j 元素的最大堆中弹出最大元素并将其存储在（新空出的）位置 j。这将对数组进行排序。

2. 使用分治策略将排序后的数组转换为二叉搜索树。（天真地说，这需要 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 31)

16 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

- user613073

Answer 3

一些基本的想法：

1. 二叉搜索树是一棵二叉树。
2. 根节点的两个子节点要么为空，要么是二叉搜索树。
3. 节点的值满足以下条件：左子节点 < 根节点 < 右子节点。

条件1不是问题 - 堆也是一棵二叉树。 条件2有问题，但建议采用自下而上的方法。 条件3也无法满足。

自下而上的意思是： - 我们从所有叶子节点开始 - 这很容易，它们都是二叉搜索树。 - 现在我们继续递归地遍历每个父节点层级直到根节点。 - 如果左子节点大于右子节点，则交换子树。 - 将根节点与两个子节点中较大的值进行交换（即右子节点）。 - 这可能还不够 - 您可能需要继续纠正右子树，直到它再次成为二叉搜索树。

这应该可以解决问题。但是，删除顶部元素并将其插入到自平衡树中将是更快/更好的方法，并且更容易实现（例如，在c++中使用标准组件如std::map）。

另一个思路：对于二叉搜索树，左根右的遍历方式可以得到排序后的值。这个过程也可以反向进行。从堆中获取排序后的值也很容易。只需要尝试将两者结合起来 - 从堆中读取并直接从排序后的值写入树中。我认为这可以在O(n)时间内完成，但我不确定是否可以原地完成，我猜想不能。

- Tobias Langner

---

这个任务不可能在 O(n) 的时间复杂度内完成。除了从堆中读取和弹出最大元素的时间复杂度为O(log n)的事实外，它还将违反排序至少需要O(n log n)的定理。建堆的复杂度为 O(n)，从二叉树中提取排序序列也需要 O(n) 的时间复杂度，因此在这两者之间，你需要进行更高复杂度的步骤。 - ltjax

问题涉及将堆树转换为二叉搜索树。我没有看到输入的堆属性被提及。如果您不使用堆属性，那么它归结为原地构建二叉搜索树，对吗？ - Manuel Salvadores