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

Question

我将堆大小设为 14，因为它是数组的初始大小，我正在做算法 clrs 简介中的问题 6.2-1。我没有像 swap 或 'to print array'

这样的其他辅助函数

堆大小我不是很清楚

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 或 i。它 永远不会 等于 left.

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

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

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

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

I have written a max_heapify code but it is not providing the required result

c++

heap

max-heap