为何MaxHeapify递归调用位置存疑却被认为正确，且引发无限循环？

你完全正确！这段代码里的递归调用位置确实是错误的，正是它导致了无限循环——你的判断非常精准。

问题根源 #

当max_loc == loc时，说明当前位置的元素已经是它所在子树的最大值，不需要再进行下滤操作了。但现在的代码不管有没有发生交换，都会无条件调用MaxHeapify(h, max_loc)，这就意味着当不需要交换时，函数会一直递归调用自己（因为max_loc等于初始的loc），最终触发无限循环，直到栈溢出。

为什么你会看到“看似相同的正确代码”？ #

你提到在很多视频和书籍里见过类似代码，大概率是这些资料里的递归调用是被包裹在if(max_loc != loc)的代码块内部的，只是可能排版或者你阅读时的疏忽让你误以为位置一样。标准的MaxHeapify实现逻辑是：只有当元素发生了交换（也就是子节点有更大的值），才需要对交换后的子节点位置继续执行下滤，否则直接终止函数。

修正后的代码 #

这里是修复了递归位置的正确版本：

void MaxHeapify(struct heap_array *h,int loc)
{
    int left,right,max_loc=loc;
    left=left_loc_child(h,loc);
    right=right_loc_child(h,loc);
    if(left !=-1 && h->array[left]>h->array[loc])
    {
        max_loc=left;
    }
    if(right!=-1 && h->array[right]>h->array[max_loc])
    {
        max_loc=right;
    }
    if(max_loc!=loc)
    {
        // 交换元素
        int temp=h->array[max_loc];
        h->array[max_loc]=h->array[loc];
        h->array[loc]=temp;
        // 只有交换后才递归调用，继续下滤
        MaxHeapify(h,max_loc);
    }
    // 没有交换的话，直接结束函数，不会进入递归
}

另外补充一点：递归实现的MaxHeapify虽然直观，但对于大型堆可能存在栈溢出的风险，你也可以考虑用迭代的方式实现下滤逻辑，避免递归的栈开销。

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