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