私は最小ヒープを使用してヒープソートを作成しようとしていましたが、それも配列ポインターを指す構造体を使用していました。今ではどちらかのいくつかの論理的な誤りがある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);
}
}
ではheapify
機能あなたは変更せた値ではないポインタを比較する必要があります
heap->array+i>heap->array+right
に
heap->array[i]>heap->array[right]
注:
array[i]
は別の記述方法である*(array+i)
ため、コードをに変更するとコードは機能します*(heap->array + i) > *(heap->array + right)
が、一般的に、角かっこを使用すると状況がはるかに明確になります。
かどうかを確認条件では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])
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加