关于二叉堆最小堆判断及方法中k、right、left与n关系的疑问

问题1：如何通过比较根节点、根节点的子节点与堆的数组长度，判断是否为最小堆？ #

首先得明确最小堆的核心性质：它是一棵完全二叉树，每个父节点的值都小于等于它的左右子节点（如果子节点存在的话）。堆通常用数组存储，我们可以利用数组的索引关系来完成判断：

假设堆的数组为heap，长度为n，数组索引从0开始（这是最常见的实现方式），那么任意父节点索引k对应的子节点索引规则是：

• 左子节点索引：2k + 1
• 右子节点索引：2k + 2

具体判断步骤如下：

• 我们只需要检查非叶子节点即可——叶子节点没有子节点，天然满足堆的条件。非叶子节点的范围是从0到(n-2)//2（整数除法），超过这个范围的都是叶子节点。
• 对每个非叶子节点k：
  1. 计算左子节点索引left = 2k + 1，如果left < n（说明左子节点存在），则必须满足heap[k] <= heap[left]，否则不是最小堆。
  2. 计算右子节点索引right = 2k + 2，如果right < n（说明右子节点存在），则必须满足heap[k] <= heap[right]，否则不是最小堆。
• 所有非叶子节点都通过检查的话，这就是一个合法的最小堆。

举个例子：数组[1,3,2,5,4]，长度n=5。非叶子节点是0、1：

• 节点0：left=1（<5），1<=3；right=2（<5），1<=2，满足条件。
• 节点1：left=3（<5），3<=5；right=4（<5），3<=4，满足条件。
  所以这是一个最小堆。

问题2：为何k、right和left需要和n做比较？ #

准确来说，我们是用>=n来判断节点/子节点是否真实存在，原因很直接：

堆的数组索引范围是0到n-1，任何索引值>=n都意味着这个位置没有对应的元素。比如：

• 当left >=n时，说明当前父节点k没有左子节点；
• 当right >=n时，说明当前父节点k没有右子节点；
• 当遍历的节点索引k超过(n-2)//2时（也就是k > (n-2)//2），这个节点是叶子节点，没有子节点，不需要再检查。

举个实例：数组长度n=4，索引0-3：

• 节点1的左子节点是2*1+1=3（<4，存在），右子节点是2*1+2=4（>=4，不存在），所以只需要检查左子节点即可。
• 节点2的左子节点是2*2+1=5（>=4，不存在），所以它是叶子节点，不用做任何子节点比较。

你看到的代码里出现k、right、left与n的比较，本质都是在判断“这个节点/子节点是否在堆的有效范围内”，既可以避免数组越界错误，也能跳过不必要的检查。

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