给定数组使用不同方法构建堆时能否得到多棵不同的完全二叉树

结论 #

可以得到不同的合法完全二叉堆结构。

原理说明 #

两种建堆方法的调整逻辑完全不同，只要最终生成的完全二叉树满足堆性质（大顶堆父节点≥子节点、小顶堆父节点≤子节点），就是合法的堆，并没有要求唯一结构。

两种方法的核心逻辑：

• 插入法（上浮建堆）：从空堆开始逐个插入元素，新元素默认放在堆的末尾，再通过上浮操作向上调整到符合堆性质的位置。
• 子树法（也叫Floyd建堆法、下沉建堆）：先把所有元素按原始顺序填充为完全二叉树，再从最后一个非叶子节点开始倒序遍历，对每个节点执行下沉操作，把对应子树调整为合法堆。

实例验证 #

我们以数组[1,2,3,4,5]构建大顶堆为例：

1. 插入法最终得到的堆数组为[5,4,2,1,3]，对应二叉树结构：根节点5，左孩子4、右孩子2；4的左孩子1、右孩子3。
2. 子树法最终得到的堆数组为[5,4,3,1,2]，对应二叉树结构：根节点5，左孩子4、右孩子3；4的左孩子1、右孩子2。

两个结构都是合法的大顶完全二叉树，结构完全不同。

内容的提问来源于stack exchange，提问作者harcourtain