c++ - 我写了一个 max_heapify 代码，但它没有提供所需的结果

Question

我将堆大小设为 14，因为它是数组的初始大小，我正在做从算法 clrs 介绍开始的问题 6.2-1。我没有其他一些辅助功能，例如交换或“打印数组”

我对堆大小不是很清楚

void max_heapify(int arr[],int i){
    int largest ;
    int n = 14;
    int left = 2*i;
    int right = (2*i) + 1;

    if (left <= n && arr[left] > arr[i])
    {
        largest = left;
    }
    else
    {
        largest = i;
    }

    if (right <= n && arr[right] > arr[i])
    {
        largest = right;
    }
    else
    {
        largest = i;
    }

    if(largest != i)
    {
        swap(arr[i], arr[largest]);
        max_heapify(arr, largest);
    }
}

int main()
{
    int arr[] = { 27,17,3,16,13,10,1,5,7,12,4,8,9,0 };
    max_heapify(arr, 3);
}

Answer 1

您的问题在于您检查right节点。你有这个：

if (left <= n && arr[left] > arr[i])
{
    largest = left;
}
else
{
    largest = i;
}

所以此时是和largest中的较大者。但是你有：arr[i]arr[left]

if (right <= n && arr[right] > arr[i])
{
    largest = right;
}
else
{
    largest = i;
}

这完全否定了您在上面所做的工作。当您完成执行此代码时，largest将等于right或 to i。它永远不可能等于left。

您需要选择这三个项目中最大的索引：arr[i]、arr[left]或arr[right]。

right您可以通过将检查替换为以下内容来修复您的代码：

if (right <= n && arr[right] > arr[largest])
{
    largest = right;
}