heapify algorithm using array indexes

I need to heapify an array and I'm using an example from my book which shows the heapify process from a binary tree. The difference is that a binary tree goes from 1 to n and an array goes from 0 to n-1 (n being the # of elements). The books algorithm for binary trees goes like this says the last non-leaf is r = n/2, n being size, and the left child is found by c = 2 * r. I modified this to use indices, which always round down to the nearest integer to r = (size-2)/2 and c = (2 * r) + 1

I tested this out with an array/binary tree with both 5 and 6 elements. A binary tree with 6 elements will have r = 3, and c = 6 and with 5 elements will have r = 2, c = 4. Since indices are just n-1, my algorithm gives r = 2, c = 5 and r = 1, c = 3 respectively. Picture for clarification so you can see what I mean
1
2
3
4
5
Binary tree                       Indices
          1                            0
      2       3                    1       2
    4   5   6  (nothing)         3   4   5 (nothing)

Thus I translated my entire heapify algorithm to
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void Heap::make(){
	//make a heap from wordArray, array holding strings
	//r = last non-leaf
	for(int r = ((size-2)/2); r > 0; r--){
		int c = (2 * r)+1; //location of left child
                cout << "checkpt1\n";
		while(r <= (size-1)){ 
//r is an index, size is # of elements, so the largest r can be is (size-1)
                        cout << "checkpt2\n";
			if((c < (size-1)) && (wordArray[c] < wordArray[c+1])){
//same with c, however I need to compare to c+1
//thus the largest c <=(size-2) aka < (size-1)
				c++;
			}
                        cout << "checkpt3\n";
			if(wordArray[r] < wordArray[c]){
				swap(wordArray[r], wordArray[c]);
				r = c;
				c = 2 * c;
			}
			else{
				break;
			}
                        cout << "checkpt4\n";
		}
	}	
}


My problem is that I keep getting a segmentation fault. I don't see how I'm going out to scope anywhere. Do I have a different problem or am I missing something that's staring me in the face?

Edit: I added checkpoints to see when the program seg faults. Running the new code results in this:
1
2
3
4
5
6
checkpt1
checkpt2
checkpt3
checkpt4
checkpt2
checkpt3

so it clearly completed one loop of the while but then fell apart on the second pass before the if statement. I still can't find anything going out of scope that would cause a seg fault
Last edited on
Topic archived. No new replies allowed.