Heap Sort Problem
I am trying to implement heap sort.
But i am not getting the correct output.
I have a structure consiting of
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:
void FixHeap(vector<Point>&HeapList, int n, int i)
data = HeapList[i].weight;
if((j<n)&&(HeapList[j].weight < HeapList[j+1].weight))
if(data >= HeapList[j].weight)
HeapList[j/2] = HeapList[j];
j = j*2;
HeapList[j/2].weight = data;
void MakeHeap(vector<Point>&HeapList, int n)
for(i=n/2; i>=1; i--)
FixHeap(HeapList, n, i);
void HeapSort(vector<Point> &HeapList, int n)
for(int i = n; i>1; i--)
temp = HeapList[i].weight;
HeapList[i] = HeapList;
HeapList = temp;
FixHeap(HeapList, i-1, 1);
I call the function from the main using
I am not sure where i am going wrong.
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?
Ah yes, you're absolutely correct, thanks for noticing that. Too late to fix my post though.
Originally Posted by oogabooga
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 :)