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.