Thread: Heap Sort Problem

I am trying to implement heap sort.

But i am not getting the correct output.

I have a structure consiting of
3 integets
int u
int v
int weight

i have then created a vector of the type of my structure, this all works fine
I need to sort the vector by the weight attribute
I can sort it using normal sort, like bubble etc, or std::sort, but I need to use HeapSort

My code so far is:

Code:

void FixHeap(vector<Point>&HeapList, int n, int i)
{
	int j;
	int data;

	j=2*i;
	data = HeapList[i].weight;

	while(j<=n)
	{
		if((j<n)&&(HeapList[j].weight < HeapList[j+1].weight))
		{
			j=j+1;
		}

		if(data >= HeapList[j].weight)
		{
			break;
		}
		else
		{
			HeapList[j/2] = HeapList[j];
		}
		j = j*2;
	}

	HeapList[j/2].weight = data;
}


void MakeHeap(vector<Point>&HeapList, int n)
{
	int i;

	for(i=n/2; i>=1; i--)
	{
		FixHeap(HeapList, n, i);
	}
}


void HeapSort(vector<Point> &HeapList, int n)
{
	MakeHeap(HeapList, n);

	int i;
	int temp;

	for(int i = n; i>1; i--)
	{
		temp = HeapList[i].weight;
		HeapList[i] = HeapList[1];
		HeapList[1] = temp;

			FixHeap(HeapList, i-1, 1);
	}
}

I call the function from the main using

Code:

HeapSort(myHeapList, myHeapList.size()-1);

I am not sure where i am going wrong.

Thank you.

Why are you passing the vector's size along with the vector? One of the points of vectors are that the size is included. You should get rid of those arguments. Also, you should use the vectors own iterators to visit each item.
It won't fix your problem, but at least it's still a good place to start, especially considering it'll make it more readable (and thus, more likely to get help).

iMalc: shouldn't it be parent = (n-1)/2 or am I missing something?

Right. I probably should've PM'ed you so you could have fixed your post. Next time...