algorithm - 是否可以在 O(n) 步骤中从 Max-Heap 构造二叉搜索树？

Question

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

请给出一个证明的答案。

Answer 1

你不能。

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

构建 BST 将确定这些节点的顺序，但排序需要 O(n log n) 时间，因此您无法在 O(n) 时间内构建 BST。