Erreur de segmentation: 11, lorsque je teste le code heapsort du livre 'Introduction to Algorithms'

Question

J'ai effectué pseudo-code de heapsort dans le livre 'Introduction of Algorithms' avec C, et une erreur est survenue: Erreur de segmentation: 11. Y at-il problème avec débordement de mémoire?

#define LEFT(i) 2*i; 
#define RIGHT(i) 2*i+1; 
#define PARENT(i) i/2; 

/************************************************/ 
/*heap_sort -- stable 
*In order to easily determine the relationship of index between parent node and child nodes, 
*available index of arr starts from 1. 
*/ 
/************************************************/ 

/* 
    Available index of arr starts from 1. 
    Length represents the last element's index. 
    Heap_size is biggest range in arr. 
*/ 
typedef struct { 
    int heap_size; 
    int length; 
    int *arr; 
} heap; 

/* 
    Node i's left_child tree and right_child tree are all max heap. 
    This function put node i's value into proper position in oder to keep a max heap. 
*/ 
void max_heapify(heap h, int i) { 
    int *arr = h.arr; 
    int left = LEFT(i); 
    int right = RIGHT(i); 
    int largest = i; 

    if (arr[left] > arr[i] && left <= h.heap_size) 
     largest = left; 
    if (arr[right] > arr[largest] && right <= h.heap_size) 
     largest = right; 

    if (largest != i) { 
     exchange(h.arr + i, h.arr + largest); 
     max_heapify(h, largest); 
    } 

    return; 
} 

/* 
    Build a max heap. 
*/ 
void build_max_heap(heap h) { 
    h.heap_size = h.length; 
    for (int i = h.length/2; i > 0; i--) //leaf nodes need not to call max_heapify 
     max_heapify(h, i); 
    return; 
} 

void heap_sort(heap h) { 
    build_max_heap(h); 
    int *arr = h.arr; 
    for (int i = h.length; i > 1; i--) { 
     exchange(arr + 1, arr + i); 
     h.heap_size--; 
     max_heapify(h, 1); 
    } 
    return; 
} 

int main() { 
    int arr[] = {1,4,9,0,2,1,6,2}; 
    int num = sizeof(arr)/sizeof(int); 
    heap h = {0, num - 1, arr}; 
    heap_sort(h); 
    for (int i = 1; i < num; i++) { 
     printf("%d,", arr[i]); 
     } 

    return 0; 
} 

tas Max est un arbre binaire dans lequel la valeur d'un nœud est plus grand que ses deux la valeur des nœuds enfants gauche et à droite.

Answer 1

Dans votre fonction max_heapify(), vous devez d'abord vérifier si left ou right est encore dans les limites - à savoir qu'ils sont <= h.heap_size, et seulement si elles sont liés, alors vous devez évaluer les valeurs de arr[left] ou arr[right]. Mais, vous faites l'inverse. Ainsi, votre programme se bloque lorsqu'il tente d'accéder à arr[left] ou arr[right] lorsque vous essayez de sortir du cadre. Cela peut être corrigé en modifiant l'ordre des conditions dans votre instruction if comme indiqué ci-dessous.

void max_heapify(heap h, int i) { 
    int *arr = h.arr; 
    int left = LEFT(i); 
    int right = RIGHT(i); 
    int largest = i; 

    /* ISSUE: You are evaluating first, checking bounds second */ 
    /* if (arr[left] > arr[i] && left <= h.heap_size) */ 

    /* Right way: Check bounds first, evaluate second */ 
    if (left <= h.heap_size && arr[left] > arr[i]) /* Right */ 
     largest = left; 

    /* ISSUE: You are evaluating first, checking bounds second */ 
    /* if (arr[right] > arr[largest] && right <= h.heap_size) */ 

    /* Right way: Check bounds first, evaluate second */ 
    if (right <= h.heap_size && arr[right] > arr[largest]) 
     largest = right; 

    if (largest != i) { 
     exchange(h.arr + i, h.arr + largest); 
     max_heapify(h, largest); 
    } 

    return; 
} 

---

Au-dessus de changement devrait résoudre votre plantage du programme.

Mais il y a encore un problème dans votre code - pas lié à votre crash du programme, mais vous donne un mauvais résultat. Vous devez également définir h.heap_size = h.length dans votre fonction heap_sort(). C'est parce que, puisque vous passez votre tas, h, en valeur, le réglage h.heap_size = h.length; en build_max_heap() fonction n'affectera pas la valeur de h.heap_size en heap_sort() fonction. Vous devez le faire dans heap_sort() fonction explicitement à nouveau.

void heap_sort(heap h) 
{ 
    build_max_heap(h); 
    int *arr = h.arr; 
    h.heap_size = h.length; /* This statement REQUIRED here */ 
    for (int i = h.length; i > 1; i--) 
    { 
      exchange(arr + 1, arr + i); 
      h.heap_size = h.heap_size - 1; 
      max_heapify(h, 1); 
    } 

    return; 
}