c - 如何在 C 中为 Min Heapsort 使用指向数组的指针？

Question

我试图使用最小堆进行堆排序，这也是一个指向数组指针的结构。现在createHeap函数或heapify函数中存在一些逻辑错误。注意：程序的其余部分不需要检查或编辑，Heapify和createHeap需要根据程序的其余部分进行修改。

   #include <stdio.h>
#include <stdlib.h>

// Max heap of length len and values stored in array
struct MinHeap{
    int size;
    int* array;
};

// Function declarations
void createHeap(struct MinHeap*);
void heapify(struct MinHeap* , int );
void heapSort(struct MinHeap*);
void swap(int*,int*);
void printArray(int*, int);

int main(){

    int numelems;
    scanf("%d",&numelems);
    int * arr = (int*) malloc(sizeof(int) * numelems);
    int i;

    for(i=0;i<numelems;i++)
    scanf("%d",&arr[i]);

    struct MinHeap* minHeap =  (struct MinHeap*) malloc(sizeof(struct MinHeap));
    minHeap->size                   = numelems;   // initialize size of heap
    minHeap->array                 = arr;     // Assign address of first element of array

    createHeap(minHeap);
    heapSort(minHeap);

    printArray(minHeap->array,numelems);
    return 0;
}

// heapSort function
void heapSort(struct MinHeap* minHeap){


    // Repeat following steps while heap size is greater than 1. 
    while (minHeap->size > 1){
        // The smallest item in Heap is stored at the root. Replace it with the last item of the heap followed by reducing the size of heap by 1.
        swap(&minHeap->array[0], &minHeap->array[minHeap->size - 1]);
        --minHeap->size;  // Reduce heap size

        // heapify the root of tree.
        heapify(minHeap, 0);
    }
} 

// function swap 2 integers
void swap(int* num1, int* num2){ 
    int temp = *num1;
    *num1    = *num2;  
    *num2    = temp; 
}

// prints an array of given size
void printArray(int* a, int len){
    int i;
    for (i = len-1; i >=0 ; i--)
        printf("%d ", a[i]);
}

void createHeap(struct MinHeap *heap)
{

    int len=heap->size-1,i;
    for(i=len;i>=0;i--)
    heapify(heap,i);
}
void heapify(struct MinHeap *heap,int i)
{
    int min;
    int right=2*i+2,left=i*2+1;
    if(right<heap->size-1 && heap->array+i>heap->array+right)
    min=right;
    else min =i;
    if(left<heap->size-1 && heap->array+i>heap->array+left)
    min=left;
    if(min!=i)
    {
        swap(heap->array+i,heap->array+min);
        heapify(heap,min);
    }   
}

Answer 1

在heapify函数中你应该比较值而不是指针所以改变

heap->array+i>heap->array+right

到

heap->array[i]>heap->array[right]

注意：array[i]只是另一种编写方式*(array+i)，因此如果将其更改为，您的代码将可以工作，*(heap->array + i) > *(heap->array + right)但总的来说，括号使事情更加清晰。

在检查 if 的条件下left，right索引在数组范围内，您应该替换left < heap->size-1为left <= heap->size-1（对right索引做同样的事情）。

在执行这些行之后

if(right<=heap->size-1 && heap->array[i]>heap->array[right])
    min=right;
else 
    min =i;

您应该min在下一次比较中使用价值

if(left<=heap->size-1 && heap->array[min]>heap->array[left])

Answer 2

// 这将保证为您工作//

void createHeap(struct MinHeap *heap)
{
    int len=heap->size-1,i;
    for(i=len;i>=0;i--)
    heapify(heap,i);
}

void heapify(struct MinHeap *heap,int i)
{
    int min;
    int right=2*i+2,left=i*2+1;
    if(right<=heap->size-1 && *(heap->array + i) > *(heap->array + right))
    min=right;
    else min =i;

    if(left<=heap->size-1 && heap->array[min]>heap->array[left]
    {
         min=left;
    }

    if(min!=i)
    {
        swap(heap->array+i,heap->array+min);
        heapify(heap,min);
    }
}