java - 从未排序数组构建最大堆会遵循二叉树属性吗？

Question

给定一个大小为 10 的未排序数组

int[] arr={∞,1,2,3,4,5,6,7,8,9,10};

如果我执行代码

public void build_heap(){
            for(int i=size/2;i>=1;i--)
                    max_heapify(i);
}

什么情况的结果数组遵循二叉树属性

( ie left subtree < root & root < right subtree )

？如何生成这样的数组？

这是正确的方法吗:不使用 build_heap ，而是继续将元素插入堆中？ (有更好的解决办法吗？)

Answer 1

不，您对数据结构感到困惑。

堆不能像 BST(二叉搜索树)那样保证排序。堆仅保证给定节点的子节点满足堆属性(即，对于最大堆，它们都小于给定的子树根，或者对于最小堆，它们都小于给定的子树根)。

另一方面，BST 保证给定子树的根的左子树上的所有键都小于根的键，并且右子树上的所有键都大于根的键。

编辑:您可以运行 heapsort在堆上，在 nlogn 时间内生成一个排序数组，从中您可以在线性时间内构造一个平衡的 BST。