Segmentierung Fehler: 11, wenn ich Heapsort-Code aus Buch 'Einführung in Algorithmen'

Question

Ich führte Pseudocode von Heapsort in Buch 'Einführung von Algorithmen' mit C, und ein Fehler aufgetreten: Segmentierung Fehler: 11. Gibt es irgendwelche Problem mit Speicherüberlauf?

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

Max Heap ist ein binärer Baum, bei dem der Wert eines Knotens ist größer als sowohl seine linken und rechten untergeordneten Knoten Wert.

Answer 1

In Ihrer max_heapify() Funktion, müssen Sie zunächst prüfen, ob left oder right noch in Grenzen ist - das heißt, sie sind <= h.heap_size, und nur dann, wenn sie in gebundener sind, dann müssen Sie die Werte von arr[left] oder arr[right] bewerten. Aber du machst das anders herum. So stürzt Ihr Programm ab, wenn es versucht, auf arr[left] oder arr[right] zuzugreifen, wenn Versuch außerhalb des Bandes sind. Dies kann behoben werden, indem Sie die Reihenfolge der Bedingungen in Ihrer if Anweisung wie unten dargestellt ändern.

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

---

Vor Änderung sollte Ihr Programmabsturz beheben.

Aber es gibt ein weiteres Problem in Ihrem Code - nicht im Zusammenhang mit Ihrem Programmabsturz, aber gibt Ihnen ein falsches Ergebnis. Sie müssen h.heap_size = h.length auch in Ihrer heap_sort() Funktion einstellen. Der Grund hierfür ist, dass die h-Wert nach Wert h.heap_size = h.length; in build_max_heap() Funktion nicht den Wert von h.heap_size in heap_sort() Funktion beeinflussen. Sie müssen das in heap_sort() Funktion erneut explizit ausführen.

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