trying to write heapify algorithm - segmentation fault

Question

I'm ultimately trying to use heapsort to alphabetically sort words that have been read in. I've never done heaps before so I'm trying to follow along with my book. I'm using cin to store the words into a dynamically allocated array, as number of words is unknown ahead of time. From separate code I know it is being read in and the array is getting larger correctly. Then I'm trying to heapify this array, but I keep getting a segmentation fault as I'm new to programming, I can't determine how to trace this back to what I did wrong. This is my heapify code:

void Heap::make(){
    //make a heap from wordArray
    //r = last non-leaf
    for(int r = size/2; r > 1; r--){
        int c = 2 * r; //location of left child
        while(r <= size){ //size is a data member of Heap
//if r has 2 children and right is larger, make c the right child
            if((c < size) && (wordArray[c] < wordArray[c+1])){
                c++;
            }
//fix if parent failed heap-order condition
            if(wordArray[r] < wordArray[c]){

                swap(wordArray[r], wordArray[c]);
                r = c;    //check that it didn't get messed up at c
                c = 2 * c;
            }
            else{
                break; //heap-order condition holds so stop
            }
        }    
    }   
}

from playing around with couts I can determine that the program works until the if(wordArray[r] < wordArray[c]) part. The elements of wordArray are stings, and the comparators work correctly from outside testing. Is this something to do with the array being dynamic or something? I'm confused as to what I'm doing wrong here.

Answer 1

You are reading out of bounds. When you check:

if((c < size)

where c is the last element, you read out of bounds here:

 if((c < size) && (wordArray[c] < wordArray[c+1])){
                                             ^

The check should be:

if((c+1 < size)

And yet another problem is here:

while(r <= size)

where r is used in the code when it is clearly out of bounds if it r == size.

For arrays of size, n, their elements go from 0 to n-1, so accessing nth element is undefined behavior.

Answer 2

You can access the nth element of an array by it's it's n-1 line arr[n-1];//this is the nth element

Segmentation fault occur here in your code

(wordArray[c] < wordArray[c+1]) // try to modify this.

Lets assume the size = 6

Whwn for() loop will run for the first time, c = 2*6 means 6, and you are accessing the arr[6] and arr[6+1] both are not valid. Array index starts from zero instead of one.