maxHeapify 和 Heapsort 没有给出正确的输出

Question

我是竞争性编码的初学者。我正在尝试实现 maxHeapify 和 HeapSort 函数，这两个函数似乎都不是 working.Trying 很多调试但不能。

    #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 代码，但这应该不会造成问题。

你的case 0 建堆差不多是对的。它从 i = n 开始。这会起作用，但效率很低。奇怪的是，你在堆排序方法中做对了。

你的heapSort几乎是正确的。但是，您忘记了每次从堆中移除时，您都需要减小堆的大小。堆的大小不是 n，而是 i。我在上次调用 maxHeapify:

时将 n 更改为 i

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);
    }
}

maxHeapify 和 Heapsort 没有给出正确的输出

maxHeapify and Heapsort not giving correct output

algorithm

heap

heapsort

data-structures

max-heap