algorithm - 在 O(n) 时间内将堆转换为 BST？

Question

我认为我知道答案并且最小复杂度是O(nlogn)。

但是有什么方法可以从O(n)复杂度的堆中创建二叉搜索树？

Answer 1

没有在 O(n) 时间内从堆构建 BST 的算法。原因是给定 n 个元素，您可以在 O(n) 时间内从它们构建一个堆。如果您有一组值的 BST，则可以通过执行中序遍历在 O(n) 时间内对它们进行排序。如果您可以在 O(n) 时间内从堆中构建 BST，那么您可以通过以下方式获得 O(n) 排序算法

1. 在 O(n) 时间内构建堆，
2. 在 O(n) 时间内将堆转换为 BST，并且
3. 在 O(n) 时间内遍历 BST 以获得排序序列。

因此，不可能在 O(n) 时间内（或在 o(n log n) 时间内，其中 o 是little-o 表示法）将堆转换为 BST。

但是，可以在 O(n log n) 时间内从堆中构建 BST，方法是重复从 BST 中取出最大值并将其作为树中最右边的节点插入。（您需要在此处存储一个指针以便快速访问；只需在根处重复插入将花费 O(n ² ) 时间。）

希望这可以帮助！