maxHeapify and Heapsort not giving correct output

Question

I am a beginner in competitive coding. I am trying to implement maxHeapify and HeapSort functions both of which seems to be not working.Trying a lot to debug but couldn't.

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    void swap(int *x, int *y)
    {
        int temp = *x;
        *x = *y;
        *y = temp;
    }
    void maxHeapify(int *arr, int n, int i)
    {
        int largest = i;
        int l = (2 * i);
        int r = (2 * i) + 1;
        while (l <= n && arr[l] > arr[largest])
            largest = l;
        while (r <= n && arr[r] > arr[largest])
            largest = r;
        if (largest != i)
        {
            swap(&arr[largest], &arr[i]);
            maxHeapify(arr, n, largest);
        }
    }
    void heapSort(int *arr, int n)
    {
        for (int i = n / 2; i >= 1; i--)
            maxHeapify(arr, n, i);
        for (int i = n; i >= 1; i--)
        {
            swap(&arr[1], &arr[i]);
            maxHeapify(arr, n, 1);
        }
    }
    int main()
    {
        int n;
        printf("\nEnter size of array\n");
        scanf("%d", &n);
        int *arr = (int *)calloc(n, sizeof(int));
        printf("\nPlease enter array elements\n");
        for (int i = 1; i <= n; i++)
            scanf(" %d", &arr[i]);
        printf("Enter Your choice\n");
        printf("1.maxHeapify\n");
        printf("2.heapSort\n");
        printf("3.Display Heap\n");
        int choice;
        scanf(" %d", &choice);
        while (1)
        {
            switch (choice)
            {
            case 1:
                for (int i = 1; i <= n; i++)
                    maxHeapify(arr, n, i);
                break;
            case 2:
                heapSort(arr, n);
                break;
            case 3:
                printf("\nThe Heap elements are\n");
                for (int i = 1; i <= n; i++)
                    printf(" %d", arr[i]);
                break;
            default:
                exit(0);
            }
            printf("\nEnter Your choice\n");
            scanf(" %d", &choice);
        }
    }

Answer 1

The basic problem is that your maxHeapify is only pushing things down one level. At most. It needs to loop and put the item into the correct place.

Given an array arr, an item i, and the heap size n, the maxHeapify function works like this:

// find the largest among arr[i], its right child, and its left child
while (i <= n) {
    l = 2*i
    r = l + 1
    largest = i
    if (l > n)
        // left node is beyond the end of the heap
        break
    if (arr[l] > arr[largest])
        largest = l
    if (r <= n && arr[r] > arr[largest])
        largest = r
    if (largest == i)
        // neither child is larger, so done
        break
    // swap node with largest child
    swap(arr, i, largest)
    i = largest
}

That's the idea. You'll need to turn it into C code, but that shouldn't pose a problem.

Your case 0 that builds a heap is almost right. It starts at i = n. That will work, but it's inefficient. Oddly, you got it right in your heapsort method.

Your heapSort is almost correct. You forgot, though, that with each removal from the heap, you need to decrease the size of the heap. The size of the heap isn't n, but rather i. I changed n to i in the last call to maxHeapify:

void heapSort(int *arr, int n)
{
    for (int i = n / 2; i >= 1; i--)
        maxHeapify(arr, n, i);
    for (int i = n; i >= 1; i--)
    {
        swap(&arr[1], &arr[i]);
        maxHeapify(arr, i, 1);
    }
}