Heaps

[bluegray]

I am studying for my final tomorrow so i redid my heap assignment. When i run this just sits there waiting for some input. I think the problem is in my upHeap function but im not sure. Any ideas what im doing wrong!

#include "header.h"

#define RANGE 100;

template<class T, class U>
void downHeap(vector<T>& vec, int first, U sort)
{
	int size = vec.size();
	int child = 2 * first;
	while(child < size) 
	{
		if(child < size -1 && sort(vec[child], vec[child + 1]))
			child++;
		if(vec[first] < vec[child])
		{
			swap(vec[first], vec[child]);
			first = child;
			child = 2 * child;
		}
		else
			child = size;
	}
}
template<class T, class U>
T remove(vector<T>& vec, U sort)
{
	T object = vec[1];
	vec[1] = vec.back();
	vec.pop_back();
	downHeap(vec, 1, sort);
	
	return object;
}
template<class T, class U>
void print(vector<T>& vec, U sort)
{
	T object;
	for(int j = 1; j < vec.size(); j++)
	{ 
		object = remove(vec, sort);
		cout << object << " ";
	}
}	
template<class T, class U> 
void upHeap(vector<T>& vec, int index, U sort)
{
	
	while(index > 1 && sort(vec[index], vec[index / 2]))
	{
		swap(vec[index], vec[index / 2]);
		index /= 2;
	}		
}

template<class T, class U>
void insert(vector<T>& vec, const T& num, U sort)
{
	int size = vec.size();
	vec.push_back(num);
	upHeap(vec, size, sort);
}

int main()
{
	int s1 = 10;
	int size = 10;
	vector<int> v1(size);
	int number;


	srand(s1);
	for(int i = 0; i < v1.size(); i++)
	{
		v1[i] = rand() % RANGE + 1;
		number = v1[i];
		insert(v1, number, less<int>());
	}
		
	cout << endl;

	print(v1, less<int>());
	cout << endl;
	print(v1, greater<int>());
	cout << endl;
 
	return 0;
}

[jsmith]

If you are using std::sort(), I'm pretty sure you are right because
sort() expects to be able to increment its first parameter (iterator) until it
reaches the second parameter (iterator), and you are passing in the
iterators in the opposite order.

You probably also want to pass pointers to sort:

sort( &vec[index/2], &vec[index] );

Also, your #define of RANGE is wrong because it should not have a semicolon on it. Consider what the does to the line

v1[i] = rand() % RANGE + 1;

when the text "100;" is substituted for RANGE.

[bluegray]

Its not std::sort(), sort just happened to be what i called it cause im passing the less<int>() and greater<int>() functions in main

[jsmith]

Sorry, this isn't much help for your specific problem, but:

It appears from your code that you are expecting vectors to be indexed 1-based, but they are 0-based (At least print() seems to make this assumption).

From a design standpoint, it is very strange to have a function called "print()" modify the container it is printing. I'd expect print() to take the vector by const reference and not modify it, if I were a programmer using your code.

[kbw]

The program is in an infinite loop because size is growing by one each time you call insert() at the bottom of the loop.

In main(), i is always vl.size() + 10.

You seem to be mixing ideas, filling a fixed size vector, then appending to it too. Are you sure you want to do both?