在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，並且在O（n）時間內步行BST以得到排序的序列。

因此，無法將堆轉換爲BST在O（n）的時間（或者在O（N log n）的時間，其中o是little-o notation）。

但是，可以通過反覆從BST中取出最大值並將其作爲樹中最右邊的節點插入，從O（n log n）時間的堆中構建BST。 （你需要在那裏存儲一個指針以便快速訪問;只需重複插入根就會花費時間。）

希望這有助於！