没有算法可以在O（n）时间内从堆中构建BST。原因是给定n个元素，您可以在O（n）的时间内从它们构建一个堆。如果您拥有一组值的BST，则可以通过顺序遍历以O（n）时间对它们进行排序。如果您可以在O（n）的时间内从堆中构建BST，则可以通过以下方式获得O（n）排序算法：
- 在O（n）时间内建立堆，
- 在O（n）时间内将堆转换为BST，并且
- 在O（n）时间中走BST以获得排序的序列。
因此，不可能在O（n）时间（或o（n log n）时间，其中o是 little-
o表示法
）中将堆转换为BST 。
但是，可以通过在O（n log
n）时间中从堆中构建BST，方法是从BST中重复取出最大值并将其插入树中最右边的节点。（您需要在此处存储一个指针以便快速访问；仅重复插入根目录将花费O（n
2）时间。）
希望这可以帮助！
