0_1_Life 0_1_Life - 4 months ago 14
C Question

Segmentation fault: 11, when I test heapsort code from book 'Introduction to Algorithms'

I performed pseudo-code of heapsort in book 'Introduction of Algorithms' with C, and an error occurred: Segmentation fault: 11. Is there any problem with memory overflow?

#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 is a binary tree in which a node's value is bigger than both its left and right child nodes' value.

sps sps
Answer

In your max_heapify() function, first you need to check if left or right is still in bounds - i.e. they are <= h.heap_size, and only if they are in bound, then you need to evaluate values of arr[left], or arr[right]. But, you are doing the other way round. So, your program crashes when it tries to access arr[left] or arr[right] when try are out-of-bound. This can be fixed by changing the order of conditions in your if statement as seen below.

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

Above change should resolve your program crash.

But there is one more issue in your code - not related to your program crash, but gives you wrong result. You need to set h.heap_size = h.length in your heap_sort() function too. This is because, since you are passing your heap, h, by value, setting h.heap_size = h.length; in build_max_heap() function will not affect the value of h.heap_size in heap_sort() function. You need to do that in heap_sort() function explicitly again.

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