maxHeapify и Heapsort не дают правильного вывода

Question

Я новичок в соревновательном кодировании. Я пытаюсь реализовать функции maxHeapify и HeapSort, обе из которых, похоже, не работают. Пытался много отладить, но не смог.

    #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

Основная проблема c заключается в том, что ваш maxHeapify толкает вещи только на один уровень вниз. В большинстве. Нужно l oop и поместить элемент в правильное место.

Учитывая массив arr, элемент i и размер кучи n, функция maxHeapify работает следующим образом это:

// 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
}

Это идея. Вам нужно превратить его в C код, но это не должно вызывать проблем.

Ваш случай 0, который строит кучу, почти верен. Это начинается в i = n. Это будет работать, но это неэффективно. Как ни странно, вы все правильно поняли в методе heapsort.

Ваш heapSort почти верен. Вы забыли, однако, что с каждым удалением из кучи нужно уменьшать размер кучи. Размер кучи не n, а i. Я изменил n на i в последнем звонке на 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);
    }
}