堆排序功能异常：最大堆正常但排序结果不符合预期

嘿，我一眼就看出问题出在哪了——你的堆排序核心循环没做对！最大堆生成正常，但排序后输出和原堆一致，说明你压根没执行「把堆顶最大值移到末尾，再重新堆化剩余元素」的关键步骤。

问题根源 #

堆排序的本质是反复提取最大堆的堆顶元素，放到数组的末尾固定住，然后对剩下的元素重新构建最大堆。你现在的代码应该是直接输出了构建好的最大堆，完全没走这个排序循环，所以结果自然不对。

修复代码（只改排序部分，不动heapify） #

假设你已经有正确的build_max_heap（构建最大堆）和不可修改的heapify函数，把堆排序的主逻辑换成下面这段就行：

def heap_sort(arr):
    n = len(arr)
    # 这部分你已经写对了，不用改
    build_max_heap(arr)
    
    # 重点！就是下面这个循环，你之前肯定没写对或者漏了
    for i in range(n-1, 0, -1):
        # 把当前堆的最大值（堆顶）交换到当前堆的最后一位
        arr[0], arr[i] = arr[i], arr[0]
        # 对剩下的前i个元素重新堆化（注意传i作为堆的大小，只处理未排序的部分）
        heapify(arr, i, 0)

为啥这么改就对了？ #

• 每次循环把堆顶的最大值挪到数组末尾，这个位置就彻底排好序了，后面不用再碰
• 然后我们把堆的大小缩小为i（因为最后一个元素已经排好），调用heapify让剩下的元素重新变成最大堆，这样下一次循环又能拿到剩余元素里的最大值
• 循环跑完，数组就从后往前被一个个最大值填满，最终自然是升序排列

举个例子验证 #

比如你的输入是[42,33,86,75,79,9]：

1. 构建最大堆后得到[86,79,42,75,33,9]
2. 第一次交换首尾：[9,79,42,75,33,86]，然后对前5个元素堆化，得到[79,75,42,9,33,86]
3. 第二次交换首尾：[33,75,42,9,79,86]，对前4个元素堆化，得到[75,33,42,9,79,86]
4. 重复这个过程，最后就得到你想要的升序结果[9,33,42,75,79,86]

关键提醒 #

确保你的heapify函数参数是(arr, heap_size, root_index)这种形式——也就是能接收当前堆的大小参数，这样我们在循环里传i的时候，它才会只处理前i个元素，不会干扰已经排好的末尾部分。毕竟你说heapify不能改，那它的参数格式肯定是符合这个要求的，不然之前构建最大堆也不会成功。

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