我看到其他书籍和文章做法不同，所以我只是想知道自己是不是对的。我把右子节点的检查嵌套在左子节点检查之内。我也见过不嵗嵌套的实现。尽管在我看来嵌套似乎更高效。

问题在于，如果没有左子节点，那么就不可能有右子节点。

第一个 if 语句检查是否有左子节点。如果没有，我们实质上是通过不做任何操作而从函数返回。如果没有左子节点，那么这是一个叶节点，已经是一个堆。

如果存在左子节点，我们进入 if 区块。我们看看子树根节点（在 i 处）或左子节点是否更大。

接着看是否有右子节点。如果没有，那么就只有根节点和左子节点；它们的比较已经完成，我们进入 if (largest != i) 区块。

如果有右子节点，我们看看它是否比当前最大值更大。然后进入 if (largest != i) 区块。

由于这是递归，我们在三种情形下到达基础情况：

• 没有左子节点，意味着当前节点是叶节点
• 左子节点存在，右子节点不存在，且左子节点不大于子树根节点
• 左子节点存在，右子节点存在，且两个子节点都不大于子树根节点

这些条件证明基本情形的逻辑完全取决于左子节点是否存在，而不是右子节点。因此我认为把右子节点的if语句嵌套在左子节点的if语句中是可以的。

请看下面的代码。

void maxHeapify(int i)
    {
        if (leftChild(i) < size()) //this node has a left child, meaning it's not a leaf node
        {
            int largest = i;

            if (heap[leftChild(i)] > heap[largest])
            {
                largest = leftChild(i);
            }

            if (rightChild(i) < size())
            {
                if (heap[rightChild(i)] > heap[largest])
                {
                    largest = rightChild(i);
                }
            }

            if (largest != i)
            {
                swap(i, largest);
                maxHeapify(largest);
            }
        }
    }

解决方案

对于 maxHeapify 的要求并没有标准化1，因此你的逻辑是否正确取决于你的需求。很可能，你的功能需求是在堆排序的层面，类似于：

如果给定节点小于（至少）它的一个子节点，就将该节点与其最大的子节点交换，并对那个子节点重复这个过程。

在这个层面上，并未规定如何执行检查，因此允许任何正确的实现。如果这符合你的需求，那么你的实现看起来是正确的。 将需求放在这个层面，而不是逐步精确地指定每一步，可以为实现提供灵活性。

例如，如果堆排序的实现要与其他排序算法进行比较（作为排序课程的一部分），让代码清晰并不需要解释为何正确，对学生有益。否则，学生可能会纠结于验证正确性，错过与其他排序策略的比较。正如你所示，嵌套条件需要这样的解释，因此在此情境下并不理想（这也解释了你为何看到如此多的非嵌套检查的示例）。

再举一个例子，广泛使用的库并不需要迎合阅读其代码的人，而是要应对各种情况。也就是说，代码的清晰度不如执行速度重要，执行速度又不如正确性重要。在这种情况下，追求速度提升的每一个小技巧都是值得的。将条件嵌套是在这条路上的又一步。

所以，是的，你可以在需要时嵗嵌套条件，结果仍然符合“实现一个堆”的要求。是否应该这样做取决于情境。为了教育他人，保持代码的直观性；为了支持他人的工作，尽量在优化方面创新；对于你自己的工作，使用一个值得信赖的库可能是最好的选择。

1我在一些情况下看到“heapify”被用来指代题目中的函数（在假设左右子树都满足堆性质的前提下强制当前节点保持堆性质），也有时用来指代把一个数组转化为堆的函数（通常对每个非叶节点调用题中的函数）。重点是，对于名为“heapify”的函数没有标准化或通用的要求。

通过对立命题进行优化

The contrapositive of "if there is no left child then there cannot be a right child" is "if there is a right child then there is a left child". These are logically equivalent.

由于我提到广泛使用的库，我在其中一个库（C++标准库实现）中查看那里怎么做的。正如预期，这段代码经过高度优化。一个有趣的优化是：在每次执行代码时不再把左子检查和右子检查嵌套在一起，而是把左子检查从重复的代码中提取出来。这是有道理的，因为如果右子节点存在，就无需检查左子节点。只有在没有右子节点时才需要检查左子节点，而这只在堆遍历的末端发生。

如果把这项优化应用到题目的代码中（用循环替代递归），它看起来会是下面的样子。这仍然遵循我先前给出的功能要求，因此它演示了实现具有多大的自由度。

void maxHeapify(int i) { // adapted from `__adjust_heap`
    int largest = i;

    while (rightChild(largest) < size())
    {
        largest = rightChild(largest);
        if (heap[largest - 1] > heap[largest])
        {
            largest--; // `largest` is now the left child
        }
        if (heap[i] >= heap[largest])
        {
            return;
        }
        swap(i, largest); // swap by indices
        i = largest;
    }
    // If `largest` has a left child but no right child
    if (leftChild(largest) < size())
    {
        largest = leftChild(largest);
        if (heap[largest] > heap[i])
        {
            swap(i, largest); // swap by indices
            // There is nothing more to do since `largest` has no children.
        }
    }
}