ヒープソートが最大ヒープで動作しない理由を理解できません

Question

heapSortアルゴリズムを動作させることができないため、数時間前から頭を引っ張ってきました。私のビルドマックス・ヒープとmax-heapifyは、正しいコードを出力し、その後、私はあなたが

からスタートアルゴリズムにCormenのイントロでヒープソートのアルゴリズムに従う（I = A.lengthを2に下ります）

then exchange A[1] with A[i] 
    decrease heap size 
    call Max-Heapify(A,1) 

Iは、[3,4,1,2,7]の配列要素から始めて、[7、4、1、2、3]であることが最大ヒープを構築するが、私が並べ替えをするとき、私は得る：[1,1,1,2,3]。

#include <stdio.h> 
#include <math.h> 

struct heap { 
int size; 
int *heaparr; 
}; 

int *heap, size; //*heap makes a pointer to the struct 

static void build_max_heap(struct heap *p) 
{ 
int arr[5] = {0}; 
arr[0] = 3; 
arr[1] = 4; 
arr[2] = 1; 
arr[3] = 2; 
arr[4] = 7; 


int count = 0; 
p->heaparr = (int *) malloc(sizeof(int) * 5); 
for (int i = 0; i < 5; i++) 
{ 
    p->heaparr[i] = arr[i]; 
    //printf("number of each element: %d ", arr[i]); 
    count++; //count is equal to 10 elements 
} 
p->size = count-1; //size of heap is 9 
printf("size is : %d", p->size); 


for (int b = floor(p->size/2-1); b >= 0; b--) 
{ 

    max_heapify(p->heaparr, b, p->size); 
    printf("pass"); 
} 
//printf("%d", p->size/2); //prints 10; 

} 

void max_heapify(int *data, int loc, int count) { 

int left, right, largest, temp; 
left = 2*(loc)+1; //2 (i which is 0) + 1 

printf("your location: %d, your count: %d \n", loc, count); 



right = left + 1; //right child 
largest = loc; 
printf("parent is: %d, left is: %d, right is: %d \n", data[loc], 
data[left], data[right]); 

// if given array of 10 so count = 10, left is 2*5 since we get floor 
of 
(p->size/2). 
if (left <= count && data[left] > data[largest]) { //count is how many 
elements in heap 
    largest = left; //update largest for location 
    printf("here left child %d is greater than parent %d \n", 
data[left], data[loc]); 
} 
if (right <= count && data[right] > data[largest]) { 
    printf("here right child (%d) is greater than parent (%d): \n", 
data[right], data[largest]); 
    largest = right; //update largest for recursion 

} 

if(largest != loc) { //original location 
    temp = data[loc]; // holds the value of the original location 
    data[loc] = data[largest]; //array location now equals 
data[largest] 
    data[largest] = temp; //data[largest] (left or right child) = value 
of original location 
    max_heapify(data, largest, count); //perculate through. 
} 
} 
void heap_display(struct heap *h) { 
int i; 
int count = h->size+ 1; 
for(i=0; i<h->size+1; ++i) { 
    printf("|%d|", h->heaparr[i]); 
} 
    printf("\n"); 
    printf("intial display is done"); 
    for (int b = h->size ; b >= 1; b--) 
{ 

    h->heaparr[0]= h->heaparr[b]; 
    h->size--; 
    max_heapify(h->heaparr, 0, h->size); 
} 
    printf("\n"); 
    h->size = 5; 


for(i=0; i<h->size; ++i) { 
    printf("|%d|", h->heaparr[i]); 
} 

//printf("\n"); */ 
} 
void heap_sort(struct heap *p) 
{ 
build_max_heap(&p); 
//printf("size: %d ", p->size); 
/* for (int i = p->size + 1; i >= 2; i--) 
{ 
    printf("fault"); 
    p->heaparr[0] = p->heaparr[i]; 
    count--; 
    max_heapify(p->heaparr, 0, count); 
} */ 
heap_display(&p); 
} 

void main() 
{ 
int count, i, no; 
struct heap h; 
heap_sort(&h); 

//int arr[10] = {4, 1,3, 2, 16, 9, 10, 14, 8, 7}; 
//heap_sort(&h, arr); 

//heap_display(&h); 

//build_max_heap(arr); 


} 

Answer 1

私はこの問題は、あなたのdisplay_heap機能でこのループであると思う：あなたが欲しい

for (int b = h->size ; b >= 1; b--) 
{ 
    h->heaparr[0]= h->heaparr[b]; 
    h->size--; 
    max_heapify(h->heaparr, 0, h->size); 
} 

はこれです：

while size > 1 
    swap the root item (0) with the last item in the heap 
    max_heapify(0) 
    decrease size 

あなたはスワップステップが欠落しているように見えます。代わりに、ルート項目を置き換えるだけです。

修正は十分に簡単です：

for (int b = h->size ; b >= 1; b--) 
{ 
    int temp = h->heaparr[0]; 
    h->heaparr[0]= h->heaparr[b]; 
    h->heaparr[b]= temp; 
    h->size--; 
    max_heapify(h->heaparr, 0, h->size); 
}