最大堆排序应输出升序序列？现有实现问题求助

你的maxHeapSort当前输出降序结果，核心问题是每次交换堆顶和末尾元素后，没有缩小堆的有效范围：heapifyDown方法依赖this.size判断子节点是否有效，但你始终用原始的堆大小，导致已经被放到末尾的最大元素又被重新纳入堆调整，最终无法得到升序序列。

修改后的maxHeapSort代码 #

protected void maxHeapSort() {
    int n = this.heap.size();

    if (n == 0) {
        return;
    }

    // 保存原始堆大小，排序后恢复避免破坏堆状态
    int originalSize = this.size;
    for (int i = n - 1; i > 0; i--) {
        // 交换堆顶（当前最大值）与未排序部分的末尾元素
        T temp = this.heap.get(0);
        this.heap.set(0, this.heap.get(i));
        this.heap.set(i, temp);

        // 缩小有效堆范围，排除已排好的末尾元素
        this.size--;
        // 对剩余有效堆进行下沉调整
        this.heapifyDown(0);
    }
    // 恢复堆的原始大小
    this.size = originalSize;
}

关键修改说明 #

1. 保存并恢复size：排序前记录原始堆大小，排序完成后恢复，避免影响堆的后续操作（比如插入、删除）。
2. 动态缩小有效堆范围：每次交换后将this.size减1，让heapifyDown只处理未排序的前i个元素，已放到末尾的最大值不再参与堆调整。

测试验证 #

针对你的测试用例[11,5,8,3,4,1]，修改后排序流程：

• 交换11和1 → 数组变为[8,5,1,3,4,11]，size=5，heapifyDown后堆结构保持最大堆特性
• 交换8和4 → 数组变为[5,4,1,3,8,11]，size=4，继续调整堆
• 重复交换与调整，最终得到升序序列[1,3,4,5,8,11]，与测试预期一致。

你的教授提供的heapifyDown方法逻辑正确，无需修改。

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