Reheapify Down

[Andrew Garcia]

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:

#include <iostream>
#include <cstdlib>
#include <algorithm>
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 <<arry[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;

}

void make_heap(int data[], size_t size)
{
	size_t i;
	size_t k;
	size_t temp;

	for(i = 1; i < size; ++i)
	{
		k = i;
		while((data[k] != data[0]) && (data[k] > 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);
	}
}

[ne555]

`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.

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

use a swap function, please.

Also, `heap_ok' is unneeded, you could simply break

[Andrew Garcia]

So this is what I changed it to, there are still a few elements in the wrong spot, not sure what i am missing?

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 . . .