从零实现heapify函数触发stack-based buffer overrun错误求助

错误根因 #

你的栈溢出报错是数组越界访问+逻辑错误导致非法写入栈内存触发的栈保护机制，具体问题有3处：

• 终止条件错误：你当前的终止判断if (k > sizeOfHeap)完全无法拦截越界访问。你的数组长度为8，合法下标范围是0~7，当k等于8的时候已经越界，你却没有拦截；同时你在访问左右孩子前没有判断孩子下标是否合法，直接读取、写入越界地址，直接破坏了栈上的保护cookie，触发报错，你输出里的异常值1012398875就是越界读取的脏数据。
• 堆调整逻辑错误：max-heapify的核心逻辑是先找到父节点、左孩子、右孩子三个节点中的最大值，只有当最大值不是父节点时才需要交换，再递归调整被交换的子树。你当前的代码完全没有判断右孩子是否存在、也没有比较三个节点的大小，哪怕父节点已经是最大值，都会强制进入else分支和右孩子交换，逻辑完全错误，会非法改写内存。
• 函数返回值不匹配：你声明heapify返回int类型，但除了终止分支外其余路径没有return值，属于语法规范问题。

修正后的代码 #

#include <iostream>

// 调整以k为根的子树为大顶堆，假设左右子树已经是大顶堆
void heapify(int* n, int k, int sizeOfHeap)
{
    int largest = k; // 初始化最大值下标为根节点
    int left = 2 * k; // 左孩子下标
    int right = 2 * k + 1; // 右孩子下标

    // 如果左孩子存在且比当前最大值大，更新最大值下标
    if (left < sizeOfHeap && n[left] > n[largest])
        largest = left;

    // 如果右孩子存在且比当前最大值大，更新最大值下标
    if (right < sizeOfHeap && n[right] > n[largest])
        largest = right;

    // 如果最大值不是根节点，交换并递归调整被交换的子树
    if (largest != k)
    {
        int temp = n[k];
        n[k] = n[largest];
        n[largest] = temp;

        heapify(n, largest, sizeOfHeap);
    }
}

int main()
{
    // arr[0]为占位符，有效元素下标1~7
    int arr[8] = {999, 3, 10, 11, 5, 2, 0, 1};
    int sizeOfHeap = 8;
    
    heapify(arr, 1, sizeOfHeap);

    // 输出数组
    for (int i = 0; i < 8; i++)
    {
        std::cout << arr[i] << " ";
    }
    return 0;
}

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