是否可以在 O(n) 步内从 Max-Heap 构建二叉搜索树？

Question

我认为这是不可能的，因为如果确实如此，人们会构建最大堆，然后用它来构建 BST，但我认为情况并非如此。

请回答并附上证据。

Answer 1

不，你不能。

堆的底层，可以包含一半以上的节点，在堆中可能是完全无序的。 （假设所有的内部节点都小于所有的叶节点）。

构建一个BST会决定这些节点的顺序，但是排序需要O(n log n)的时间，所以你不能在O(n)时间内构建一个BST。