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

Question

I took heap size as 14 as it is the initial size of the array, I was doing question 6.2-1 from introduction to algorithms clrs. I did not some other helper function like swap or 'to print array'

I am not very clear on heap size

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

Your problem is in your checking of the right node. You have this:

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

So at this point, largest is the larger of arr[i] and arr[left]. But then you have:

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

This totally negates the work you did above. When you finish executing this code, largest will either be equal to right or to i. It can never be equal to left.

You need to pick the index of the largest of those three items: arr[i], arr[left], or arr[right].

You can fix your code by replacing the right check with this:

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