### Reheapify Down

So I am working on this heap sort program I have an algorithm from my book that i am trying to follow, what i cant seem to figure out though is the reheapify_down function. There is a part in the pseudocode it says "if there is only one child then big_child_index will be set to the index of this one child" this is where I think im going wrong but maybe you guys can help. I know the make heap and the heapsort functions will work its the reheapify thats causing me problems. Thanks! Here it is:
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102`` ``````#include #include #include using namespace std; void heapsort(int data[], size_t n); void make_heap(int data[], size_t size); void reheapify_down(int data[], size_t n); void heapsort(int data[], size_t n); int main() { int arry[] = {21, 35, 22, 27, 23, 45, 42, 19, 4, 5}; cout <<"Original Data: "; for(int i = 0; i < 10; i++) { cout << arry[i] << " "; } cout << endl; heapsort(arry, 10); //make_heap(arry, 10); cout <<"\nNew Data: "; for(int i = 0; i < 10; i++) { cout < data[(k -1) / 2])) { temp = data[k]; data[k] = data[(k-1)/2]; data[(k-1)/2] = temp; k = (k-1)/2; } } } void reheapify_down(int data[], size_t n) { size_t current; size_t big_child_index; bool heap_ok; current = 0; heap_ok = false; while((!heap_ok) && ((2 * current) + 1 < n) && ((2 * current) + 2 < n)) { if(data[(2*current) + 1] > data[current] && ((2*current) + 1 < n)) { big_child_index = (2 * current) + 1; } if(data[(2*current)+2] > data[current] && ((2*current)+2 < n)) { big_child_index = (2 * current) + 2; } if(data[current] < data[big_child_index]) { int temp = data[current]; data[current] = data[big_child_index]; data[big_child_index] = temp; current = big_child_index; } else heap_ok = true; } } void heapsort(int data[], size_t n) { size_t unsorted; make_heap(data, n); cout << "Heap Data: "; for (int i = 0; i < n; ++i) { cout << data[i] << " "; } unsorted = n; while(unsorted > 1) { --unsorted; swap(data[0], data[unsorted]); reheapify_down(data, unsorted); } }``````
`big_child_index' is used uninitialized.
`((2 * current) + 1 < n) && ((2 * current) + 2 < n)` I assume that `n' is the size of the heap, so you are expecting that the note has 2 children.
No need to recheck those conditions inside the loop.

 ``1234`` `````` int temp = data[current]; data[current] = data[big_child_index]; data[big_child_index] = temp; current = big_child_index;``````

Also, `heap_ok' is unneeded, you could simply `break`
So this is what I changed it to, there are still a few elements in the wrong spot, not sure what i am missing?

 ``12345678910111213141516171819202122232425262728293031323334`` ``````void reheapify_down(int data[], size_t n) { size_t current; size_t big_child_index; bool heap_ok; current = 0; heap_ok = false; while((!heap_ok) && ((2 * current) + 1 < n) && ((2 * current) + 2 < n)) { if(data[(2*current) + 1] > data[current]) { big_child_index = (2 * current) + 1; } if(data[(2*current)+2] > data[current]) { big_child_index = (2 * current) + 2; } if(data[current] < data[big_child_index]) { swap(data[big_child_index], data[current]); //int temp = data[current]; //data[current] = data[big_child_index]; //data[big_child_index] = temp; current = big_child_index; } else heap_ok = true; } }``````

The 19 4 5 are out of place which would be the leaf elements of the tree, so im not sure how im missing these?

Original Data: 21 35 22 27 23 45 42 19 4 5
Heap Data: 45 27 42 21 23 22 35 19 4 5
New Data: 19 4 21 22 23 5 27 35 42 45
Press any key to continue . . .
Topic archived. No new replies allowed.