c - Cormen 在 C 中实现的 Heapsort 算法，无法正常工作

Question

#include <stdio.h>
#include <math.h>
#define MAXSIZE    100
#define LEFT(X)    (2*(X))
#define RIGHT(X)   ((2*(X)) + 1)
#define Parent(X)  ((X)/2)

void inputElements(int *arr ,int *size);
void printElements(int *arr , int size);
void max_heapify(int *arr , int index , int heap_size);
void build_max_heap(int *arr,int heap_size);
void heap_sort(int *arr , int heap_size);

int main(){

    int arr[MAXSIZE] ;
    int size = 0;

    inputElements(arr , &size);
    printElements(arr , size);

    heap_sort(arr, size);
    printf("Array after Heap Sort");
    printElements(arr , size);


    return 0 ;
}


void inputElements(int *arr ,int *size){


    printf("Enter Size of Array(max %d)..\n" , MAXSIZE);
    scanf("%d",size);

    printf("Enter the array Elements..\n");
    for(int i=0 ; i<(*size) ; i++){
        scanf("%d" , (arr+i));
    }

}

void printElements(int *arr , int size){

    printf("Printing Array Elements..\n");
    for(int i=0 ; i<size ; i++){
        printf("%d\n" , arr[i]);
    }

}


void build_max_heap(int *arr,int heap_size){

    for(int i=((heap_size)/2) ; i>=0 ; i--){

        max_heapify(arr , i , heap_size);
    }

}

void max_heapify(int *arr , int index , int heap_size){

    int l ,r , largest , temp;

    l = LEFT(index);
    r = RIGHT(index);

    if ((l < heap_size) && (arr[l] > arr[index])) {
        largest = l;
    } else {
        largest = index;
    }

    if ((r < heap_size) && (arr[r] > arr[index])) {
        largest = r;
    }

    if (largest != index) {
        temp = arr[index];
        arr[index] = arr[largest];
        arr[largest] = temp;
        max_heapify(arr , largest , heap_size);
    }

}



void heap_sort(int *arr , int heap_size){

    int temp = -1 , i ;
    build_max_heap(arr,heap_size);

    for (i = (heap_size-1); i >= 1; i--) {

        temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        heap_size = heap_size-1;
        max_heapify(arr , 0 , heap_size);
    }

}

main 函数首先询问数组的大小，然后将要排序的数字存储在数组中。 heap_sort函数首先调用build_max_heap将数组转为堆，对数组进行排序。

当我在一组数字上运行算法时说: 90后 45 33 22 66 4

运行算法后的输出为L 4个 45 22 33 66 90

无法追踪索引出错的地方。

Answer 1

我相信您的 Left 和 right 功能可能会因一个错误而关闭。左(0)不应该是0(应该是1)，右(0)不应该是1(应该是2)。 1左边不应该是2(应该是3)，1右边不应该是3(应该是4)等等——IdeaHat