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

Question

我认为我知道答案,最小的复杂性是O(nlogn).

但是,有没有什么办法可以在O(n)复杂度中从堆中创建二进制搜索树？

Answer 1

在O(n)时间内没有用于从堆构建BST的算法.原因是给定n个元素,您可以在O(n)时间内从它们构建堆.如果您有一组值的BST,则可以通过执行inorder遍历在O(n)时间内对它们进行排序.如果你可以在O(n)时间从堆构建BST,那么你可以通过O(n)排序算法

1. 在O(n)时间内构建堆,
2. 在O(n)时间内将堆转换为BST,和
3. 在O(n)时间内走BST以获得排序的序列.

因此,不可能在O(n)时间(或在o(n log n)时间内将堆转换为BST,其中o是小符号).

但是,可以通过重复从BST中取出最大值并将其作为树中最右边的节点插入,在O(n log n)时间内从堆构建BST.(您需要在那里存储指针以便快速访问;只需在根处重复插入将花费O(n ²)时间.)

希望这可以帮助!