在O（n）时间转换堆到BST？ [英] Converting a heap to a BST in O(n) time?

问题描述

我想我知道答案，最小的复杂性是 O（nlogn）

I think that I know the answer and the minimum complexity is O(nlogn).

但有什么办法，我可以从堆的二叉搜索树中的 O（N）的复杂性？

But is there any way that I can make an binary search tree from a heap in O(n) complexity?

推荐答案

没有算法从堆为O建设BST（n）的时间。这样做的原因是，给定n个元素，你可以从他们的O（n）的时间建立一个堆。如果你有一个BST为一组值，你可以做一个序遍历对它们进行排序在O（n）时间。如果你可以从一个堆为O建立BST（n）的时间，然后你可以用

There is no algorithm for building a BST from a heap in O(n) time. The reason for this is that given n elements, you can build a heap from them in O(n) time. If you have a BST for a set of values, you can sort them in O(n) time by doing an inorder traversal. If you could build a BST from a heap in O(n) time, you could then have an O(n) sorting algorithm by

1. 在Ø构建堆（n）的时间，
2. 在澳堆转换为BST（n）的时间，和
3. 走在BST在O（n）的时间来排序的序列。

因此​​，不能将堆转换为BST在O（n）时间（或O（N log n）的时间，其中o是的little-o符号 ）。

Therefore, it is not possible to convert a heap to a BST in O(n) time (or in o(n log n) time, where o is little-o notation).

然而，有可能为O通过反复出队从BST的最大值并将其插入作为树中最右边的节点从一个堆构建BST（正log n）的时间。 （你需要有存储指针快速访问;刚插入在根反复将采取为O（n ² ）的时间）

However, it is possible to build a BST from a heap in O(n log n) time by repeatedly dequeueing the maximum value from the BST and inserting it as the rightmost node in the tree. (You'd need to store a pointer there for fast access; just inserting at the root repeatly would take O(n²) time.)

希望这有助于！

这篇关于在O（n）时间转换堆到BST？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！