セグメンテーションフォールト：11、「アルゴリズム紹介」

Question

「アルゴリズム紹介」のCでヒープソースの擬似コードを実行しましたが、エラーが発生しました：セグメンテーションフォールト：11.メモリオーバーフローの問題？

#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_heapify()機能で

Answer 1

は、まずあなたはleftまたはrightが境界内にまだあるかどうかを確認する必要がある - すなわち、彼らは<= h.heap_sizeであり、それらはバウンドしている場合にのみ、あなたはarr[left]、またはarr[right]の値を評価する必要があります。しかし、あなたは他のやり方をしています。したがって、試行が外れたときにarr[left]またはarr[right]にアクセスしようとすると、プログラムがクラッシュします。これは、以下のようにifステートメントの条件の順序を変更することで修正できます。変更の上

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

---

あなたのプログラムのクラッシュを解決する必要があります。

あなたのコードにはもう1つの問題があります。プログラムのクラッシュとは関係ありませんが、間違った結果をもたらします。 heap_sort()機能にもh.heap_size = h.lengthを設定する必要があります。これは、hのヒープを渡しているため、h.heap_size = h.length;をbuild_max_heap()に設定しても、h.heap_sizeの値がheap_sort()の機能に影響しないためです。 heap_sort()の機能を明示的に再度実行する必要があります。

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