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

基本问题是，您的maxHeapify只会将内容推低一级。最多。它需要循环并将其放入正确的位置。

给出数组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);
    }
}