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

Your main problem is the formula for obtaining the children and parent of a node.
The algorithm is often described in a manner that would make the head at index 1 and its children at indexes 2 and 3 (children = 2n and 2n+1, parent = n/2)
However in practice arrays start at zero and so you need the head to be at index 0 and its children at indexes 1 and 2 (children = 2n-1 and 2n, parent = (n+1)/2)

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

Originally Posted by oogabooga

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

Ah yes, you're absolutely correct, thanks for noticing that. Too late to fix my post though.

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

Nah I was off watching youtube crap anyway