堆排序为何从i = n/2开始？及最小堆排序代码排障

1. SWAP函数失效问题 #

你的SWAP函数采用传值调用，修改的只是函数内部的参数副本，原数组中的元素根本没发生交换。堆排序的核心步骤就是将堆顶最小元素和末尾元素交换，再重新调整堆，这个函数失效直接导致排序后数组仍维持堆结构，而非有序数组。

修复方案：

• 方案一：改为传引用调用，让函数直接修改原数组元素：

void SWAP(element &root, element &target) { 
    element temp = root;
    root = target;
    target = temp;
}

调用时去掉多余的第三个参数：SWAP(a[1], a[i + 1]);

• 方案二：直接在heapSort里手动交换，省去SWAP函数：

for (i = n - 1; i > 0; i-- ) {
    element temp = a[1];
    a[1] = a[i + 1];
    a[i + 1] = temp;
    adjust(a, 1, i);
}

2. adjust函数的数组引用问题 #

adjust函数参数是element e[]，但内部直接使用全局数组a，逻辑不严谨且复用性差。建议把内部所有a替换为参数e：

void adjust(element e[], int root, int n) {
    int child, rootkey;
    element temp = e[root];
    rootkey = e[root].key;
    child = 2 * root;
    while (child <= n) {
        if ((child < n) && (e[child].key > e[child + 1].key))
            child++;
        if (rootkey < e[child].key)
            break;
        else {
            e[child / 2] = e[child];
            child *= 2;
        }
    }
    e[child / 2] = temp;
}

3. 缺少排序结果输出 #

代码排序后没有打印逻辑，导致你看不到有序数组。在P1函数的heapSort(a, n);之后添加输出代码：

cout << "排序结果：";
for (int i = 1; i <= n; i++) {
    cout << a[i].key << " ";
}
cout << endl;

堆是完全二叉树，用数组存储时，下标满足：

• 下标为i的节点，左孩子下标是2*i，右孩子是2*i+1
• 下标大于n/2的节点都是叶子节点，叶子节点没有子节点，本身就符合堆的定义（最小堆中叶子节点没有更小的子节点，自然满足堆性质）

初始化堆时，只需从最后一个非叶子节点（下标n/2）开始，往前遍历到根节点（下标1），逐个调用adjust调整为堆结构。这样能保证每个节点都满足堆性质，最终整个数组成为最小堆。如果从根节点开始调整，会重复处理已调整好的子树，效率更低，而从n/2开始是最高效的初始化方式。

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