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

Question

我试图使用最小堆进行堆排序，同样使用指向数组指针的结构。现在 createHeap 函数或 heapify 函数中存在一些逻辑错误。程序的Note:Rest不需要检查和编辑，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]

Note: array[i] is just another way of writing *(array+i), so your code would work if changed it to *(heap->array + i) > *(heap->array + right) but in general, the brackets makes things much clearer.

在检查 left、right 索引是否在数组范围内的条件下，您应该将 left < heap->size-1 替换为 left <= heap->size-1（与 [= 做同样的事情） 19=]索引）。

这些行执行后

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

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

how to use pointers to array for Min Heapsort in C?

c

pointers

structure

min-heap

heapsort