问题描述
我想我知道答案，最小的复杂性是 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
- 在Ø构建堆（n）的时间，
- 在澳堆转换为BST（n）的时间，和
- 走在BST在O（n）的时间来排序的序列。
因此，不能将堆转换为BST在O（n）时间（或O（N log n）的时间，其中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？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！