你的堆排序代码出现部分输入排序失效的问题，核心原因在于堆构建（buildheap）函数的逻辑错误，同时还有几处潜在的越界风险需要修正。下面逐一拆解问题并给出修复方案：

1. 堆构建函数（buildheap）的致命错误 #

构建大顶堆的正确逻辑是从最后一个非叶子节点开始，向上遍历到根节点，逐个调用heapify调整堆结构。但你的代码中：

void buildheap(int *arr,int i,int j)
{
    for(;i<=(i+j)/2;i++)
        heapify(arr,i,j);
}

存在两个严重问题：

• 遍历顺序错误：从根节点（i=0）开始向下遍历，这会导致后续节点的调整破坏前面已经调整好的堆结构，无法正确构建大顶堆。
• 循环条件错误：i<=(i+j)/2是一个动态变化的条件，随着i递增，(i+j)/2也会变大，导致循环无法正确终止在最后一个非叶子节点。

修复方式：
从最后一个非叶子节点（索引为(j-1)/2）开始，反向遍历到根节点（索引0）：

void buildheap(int *arr, int j)
{
    // 从最后一个非叶子节点开始向上调整
    for(int k = (j-1)/2; k >= 0; k--)
        heapify(arr, k, j);
}

同时简化参数，因为构建堆只需要数组的最后一个索引即可，不需要起始索引i。

2. heapify函数的越界风险 #

你的heapify中判断子节点存在的顺序错误：

if(arr[max]<arr[(2*i)+1] && (2*i)+1<=n)

C++的逻辑与&&是短路求值，但你先访问数组元素再判断下标是否合法，当下标(2*i)+1超过n时，会触发数组越界访问（未定义行为）。

修复方式：
先判断下标是否在合法范围内，再比较元素大小：

if((2*i)+1 <= n && arr[max] < arr[(2*i)+1])
    max = (2*i)+1;
if((2*i)+2 <= n && arr[max] < arr[(2*i)+2])
    max = (2*i)+2;

3. heapsort函数的参数简化与逻辑优化 #

原heapsort函数的参数i固定为0，没有必要作为参数传递，可以直接在函数内使用0作为堆顶索引，同时调整buildheap的调用：

int* heapsort(int *arr, int n)
{
    buildheap(arr, n-1); // 传递最后一个元素的索引
    int *b = new int[n];
    int index = 0;
    int heapSize = n-1;
    while(heapSize >= 0)
    {
        b[index++] = arr[0]; // 取出堆顶元素（最大值）
        arr[0] = arr[heapSize--]; // 用最后一个元素替换堆顶
        heapify(arr, 0, heapSize); // 调整堆结构
    }
    return b;
}

4. 主函数的内存泄漏修复 #

原代码没有释放动态分配的内存，长期运行会导致内存泄漏，建议在主函数末尾添加内存释放逻辑：

int main()
{
    int *arr, n;
    cout << "how many elements?" << endl;
    cin >> n;
    cout << "enter elements : " << endl;
    arr = new int[n];
    for(int i=0; i<n; i++)
        cin >> arr[i];
    int *sortedArr = heapsort(arr, n); // 传递数组长度n
    printarr(sortedArr, n-1); // 传递最后一个元素的索引
    // 释放动态分配的内存
    delete[] arr;
    delete[] sortedArr;
    return 0;
}

完整修复后的代码 #

#include<iostream>
using namespace std;

void printarr(int *arr, int n)
{
    // 当传入n为数组最后一个索引时，0到n正好遍历所有元素
    for(int i=0; i<=n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

void heapify(int *arr, int i, int n)
{
    int max = i;
    // 先判断下标合法性，再比较元素
    if((2*i)+1 <= n && arr[max] < arr[(2*i)+1])
        max = (2*i)+1;
    if((2*i)+2 <= n && arr[max] < arr[(2*i)+2])
        max = (2*i)+2;
    if(i != max)
    {
        swap(arr[max], arr[i]);
        heapify(arr, max, n);
    }
}

void buildheap(int *arr, int j)
{
    // 从最后一个非叶子节点开始向上调整堆
    for(int k = (j-1)/2; k >= 0; k--)
        heapify(arr, k, j);
}

int* heapsort(int *arr, int n)
{
    buildheap(arr, n-1);
    int *b = new int[n];
    int index = 0;
    int heapSize = n-1;
    while(heapSize >= 0)
    {
        b[index++] = arr[0];
        arr[0] = arr[heapSize--];
        heapify(arr, 0, heapSize);
    }
    return b;
}

int main()
{
    int *arr, n;
    cout << "how many elements?" << endl;
    cin >> n;
    cout << "enter elements : " << endl;
    arr = new int[n];
    for(int i=0; i<n; i++)
        cin >> arr[i];
    int *sortedArr = heapsort(arr, n);
    printarr(sortedArr, n-1);
    // 释放动态分配的内存
    delete[] arr;
    delete[] sortedArr;
    return 0;
}

测试验证 #

输入你提供的数组{1,5,2,4,3,6,0,7,9,8}（n=10），修复后的代码会输出正确的降序排列：9 8 7 6 5 4 3 2 1 0，完全符合预期。

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