Min-Max Heap中如何O(1)从索引获取节点层级？兼谈完全二叉树层级与索引关系

在0-based索引的完全二叉树中（根节点索引为0），节点索引i和其所在层级k（根为第0层）存在明确的数学关联：

• 层级k是满足 2^k ≤ i+1 < 2^(k+1) 的整数，等价于 k = floor(log₂(i+1))。
• 直观来说，层级等于节点索引i+1的二进制表示的位数减1，例如：
  • 索引0 → i+1=1（二进制1）→ 位数1 → 层级0
  • 索引1 → i+1=2（二进制10）→ 位数2 → 层级1
  • 索引3 → i+1=4（二进制100）→ 位数3 → 层级2

要在常数时间判断节点是否处于偶数层（min level），可以利用位运算快速计算层级的奇偶性，无需遍历或递归：

int IsOnMinLevel(Heap H, int i) {
    // 先检查索引是否有效
    if (i < 0 || i >= H->count) {
        return 0; // 无效节点直接返回0（非min level）
    }

    int x = i + 1;
    // 利用GCC内置函数计算前导零个数，快速得到层级
    int leading_zeros = __builtin_clz(x);
    int level = 31 - leading_zeros; // 根节点对应层级0

    // 判断层级是否为偶数
    return (level % 2 == 0) ? 1 : 0;
}

补充说明： #

• 兼容性替代方案：如果编译器不支持__builtin_clz，可以用固定次数的位运算计算层级（对于32位整数，最多循环31次，仍属于常数时间）：

  int get_level(int i) {
      int x = i + 1;
      int level = 0;
      while (x > 1) {
          x >>= 1;
          level++;
      }
      return level;
  }
  

  只需将原函数中的层级计算部分替换为int level = get_level(i);即可。
• 层级定义适配：若题目中层级从1开始计数（根为第1层），则偶数层对应层级2、4...，此时判断条件需改为(level % 2 == 1)（原计算的层级0对应实际层级1，层级1对应实际层级2，以此类推）。

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