最大堆最小元素位置及堆数组叶节点索引规则相关问询

前提：以下讨论默认基于1起始索引的数组实现的完全二叉树最大堆，所有元素互不相同。

原问题结论 #

最大堆的最小元素只能出现在所有叶节点对应的数组位置，即索引范围为⌊n/2⌋ + 1 ~ n（n为堆总节点数）的任意位置。

核心疑问解答 #

• 为什么不用「叶节点」直接表述，而是引入⌊n/2⌋ +k (k≥1)的写法？
  「叶节点」是完全二叉树的逻辑结构概念，而公式化的索引表述是直接对应数组存储的可落地写法，没有歧义，不管是理论证明还是代码实现，都可以直接通过数组长度n计算出最小元素的可能范围，不需要额外遍历判断节点是否为叶节点，实用性更强。

• 为什么最小元素一定在数组后半段的叶节点中？
  最大堆的核心规则是任意父节点的值一定大于它的所有子节点的值。如果一个节点不是叶节点，说明它至少有一个子节点，那它的值一定比子节点大，自然不可能是整个堆的最小值。
  你提到的「高度为1的子节点」本质是非叶节点，它必然存在比它更小的子节点，所以不可能是最小值。只有没有子节点的叶节点不存在更小的后代，所以最小值只能出现在叶节点，而叶节点刚好对应数组的后半段。

补充疑问解答 #

首先明确数组实现完全二叉树的下标映射规则：索引为i的节点，左子节点索引为2i，右子节点索引为2i+1，父节点索引为⌊i/2⌋。

1. 整个堆的最后一个节点索引为n，它的父节点索引为⌊n/2⌋，这就是最后一个存在子节点的节点，也就是最后一个非叶节点。
2. 所有索引大于⌊n/2⌋的节点，计算它的左子节点索引2i一定大于n，说明不存在子节点，自然就是叶节点，所以叶节点的索引范围是⌊n/2⌋+1 ~ n（你提到的「叶节点索引到⌊n/2⌋+n」属于笔误，堆总节点数只有n，最大索引就是n）。
3. 结合你给出的叶节点数量公式Ceil(n/2)验证：该区间的节点总数为n - (⌊n/2⌋ +1) +1 = n - ⌊n/2⌋，刚好等于Ceil(n/2)，和公式完全吻合。

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