首页 文章

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

提问于
浏览 次
17

我们给出了一个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] > A[2i] and A[i] > A[2i+1]

是否存在相当快速的就地算法来重新排列数组的元素，以便生成的二叉树（如上所述）是二叉搜索树？

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

例如，上述阵列的重新洗牌将是

[4 2 6 1 3 5 7]

它对应于二叉搜索树

4
    /    \
   2       6
  /  \    / \
 1    3   5  7
c algorithm heap binary-tree

4 回答

  • 7

    首先，我们注意到，我们可以 - 不失一般性 - 假设我们在二叉树中有元素1,2,3，... 2^m-1 . 所以，从现在开始，我们假设我们有这些数字 .

    然后，我的尝试将是一个函数将已排序的数组（即 1 2 3 4 5 ）转换为表示已排序的二叉树的数组 .

    在具有 (2^m)-1 元素的已排序二进制树中，我们始终认为树的"bottom"包含所有不均匀的数字，例如， for m=3 ：

    4
  2     6
 1 3   5 7

    这意味着，在相应的数组中，我们得到的最后一个数字都是不均匀的数字：

    4 2 6 1 3 5 7
      -------
         ^
         uneven numbers!

    因此，我们可以通过确保相应数组中的最后 2^(m-1) 数字都是不均匀数字来构造二进制树的最后"row" . 因此，我们需要为最后一行做的就是构造一个函数，将具有不均匀索引的位置处的所有元素移动到最后一行 .

    因此，现在让我们假设我们有一个例程 - 给定一个排序数组作为输入 - 正确 Build 最后一行 .

    然后我们可以调用整个数组的例程来构造最后一行，而所有其他元素都保持排序 . 当我们在数组 1 2 3 4 5 6 7 上应用此例程时，我们有以下情况：

    2 4 6 1 3 5 7
      -------
         ^
         correct!

    在第一轮之后，我们将例程应用于剩余的子数组（即 2 4 6 ），它构造了我们的二叉树的第二个"row"，而我们保留其余元素不变，因此我们得到以下结果：

    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，以便整个内容完全就地工作 .

    对不起，我不能进一步详细说明，但我认为你可以得到这个想法 .

    回复于
  • 0

    设n = 2m - 1.在线性时间内，我们都可以生成最大堆并按排序顺序提取二叉搜索树的元素，因此我们所希望的最好（假设基于比较的算法）是O（n记录n）时间和O（1）空间 . 这是一个这样的算法 .

    • 对于j = n下降到1，从j元素max-heap中弹出max元素并将其存储在（新腾出的）位置j . 这会对数组进行排序 .

    • 使用分而治之策略将已排序的数组转换为二叉搜索树 . （天真这是Omega（log n）空间，但我相信我们可以将堆栈压缩为O（1）log（n）位字 . ）

    一个 . 树化少于根的元素 .

    湾树化大于根的元素 .

    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

    回复于
  • 2

    Just some basic ideas:

    • 二叉搜索树是二叉树 .

    • 根的两个子节点都是零或自己的二叉搜索树

    • 这些值满足以下条件：left child <root <right child

    条件1不是问题 - 堆也是二叉树 . 条件2存在问题，但建议采用自下而上的方法 . 条件3也不满足 .

    自下而上意味着： - 我们从所有叶子开始 - 这是没有问题的，它们是二叉搜索树 . - 现在我们继续通过递归遍历每个级别的父级到根 . - 如果左孩子比右孩子大，则交换子树 . - 用2个孩子的较大值（它是正确的孩子）交换根 - 这可能还不够 - 你可能需要继续纠正正确的子树，直到它再次成为二叉搜索树 .

    这应该工作 . 但仍然 - 删除顶部元素并将其插入自 balancer 树将是更快/更好的方法，并且更容易实现（例如，使用标准组件，如c中的std :: map） .

    对于二叉搜索树， Another idea: 包含左右根遍历树的属性获取排序值 . 这可以反过来做 . 获取从堆中排序的值也应该很容易 . 只是尝试将它结合起来 - 从堆中读取并直接从排序值中写入树 . 这可以在O（n）中完成，我认为 - 但我不确定它是否可以在适当的地方完成 - 我猜不是 .

    回复于
  • 1

    逐个选择原始数组的数组项，然后将它们添加到二进制搜索树中，您可以保持 balancer ，同时始终确保根位于树的正中间 . 例如，通过跟踪根的左侧和右侧的节点数量 .

    回复于

相关问题