堆高度计算是否包含根节点？同值子节点交换规则确认

1. 堆高度的计算规则 #

堆高度目前没有全行业统一的强制计算标准，两种定义均被广泛使用，核心差异是统计维度不同：

• 按路径节点数统计：高度为根节点到最远叶子节点的路径上包含的节点总数，根节点计入高度。这种定义下h高度的堆元素数量范围为 2^(h-1) ≤ n ≤ 2^h -1，国内绝大多数本科数据结构教材、入门算法资料都采用这种定义。
• 按路径边数统计：也就是NIST的标准树高度定义，高度为根节点到最远叶子节点的路径上包含的边数，根节点高度记为0。这种定义下h高度的堆元素数量范围为 2^h ≤ n ≤ 2^(h+1) -1，《算法导论》等国外经典算法教材、多数工业界实现参考文档都采用这种定义。

不存在明确规则要求必须不计入根节点统计高度，实际使用时只要在同一场景下保持定义统一即可，通常相关文档、教程都会在首次提及堆高度时明确对应的统计规则。

2. 左右子节点值相等时的堆调整规则 #

没有强制的左右选择优先级要求，可以任选其一交换：

• 堆的核心性质只要求父节点的值满足大顶堆/小顶堆的大小关系约束，左右子节点值相等时，无论和哪一个交换，都不会破坏堆的核心性质，也不会影响堆操作的时间复杂度。
• 部分具体实现可能会因为编码便利性固定优先选择左节点或者右节点交换，比如很多实现为了简化分支逻辑，会默认先校验左子节点再校验右子节点，值相等时就会优先和左子节点交换，但这只是实现层面的自定义选择，不是堆结构本身的规则要求。

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