How can I print order of odd numbers first and then even instead of smaller numbers using heapsort?

Question

Suppose there is an array consisting of numbers 1,2,4,3,5,6,7 .I want to print 1,3,5,7,2,4,6 using heapsort. I've been trying to modify basic heapsort but not been able to have correct output.

Can you please help?

#include<bits/stdc++.h>
using namespace std;

int heapsize;

int make_left(int i)
{
    return 2*i;
}
int make_right(int i)
{
    return (2*i)+1;
}
void max_heapify(int a[],int i)
{
  //  cout<<heapsize<<endl;
    int largest=i;
   // printf("current position of largest is %d and  largest is %d\n",largest,a[largest]);


    int l=make_left(i);
    int r=make_right(i);
 //   printf("current position of left is %d and  left element is %d\n",l,a[l]);
   // printf("current position of right is %d and  right element is %d\n",r,a[r]);

    if(a[l]>=a[largest] && l<=heapsize && a[l]%2!=0)
        largest=l;
    if(a[r]>a[largest] && r<=heapsize && a[l]%2!=0)
        largest=r;
    //printf("Finalcurrent position of largest is %d and  largest is %d\n",largest,a[largest]);

    if(largest!=i)
    {
        swap(a[i],a[largest]);
        max_heapify(a,largest);
    }
}
void buildmax(int a[],int n)
{
 for (int i=n/2;i>=1;i--)
    {
     //   printf("main theke call\n");
        max_heapify(a,i);
    }
}
void heapsort(int a[],int n)
{
    buildmax(a,n);
//    printf("After being buildmax\n");
  //  for (int i=1;i<=n;i++)
    //{
        //printf("i is %d\n",i);
      //  cout<<a[i]<<endl;

    //}
    for (int i=n;i>=2;i--)
    {
      //   printf("1st element is %d and last elemenet is %d\n",a[1],a[heapsize]);

        swap(a[1],a[heapsize]);
        //printf("1st element is %d and last elemenet is %d\n",a[1],a[heapsize]);
        heapsize--;
        max_heapify(a,1);
    }

}


int main()
{

    int n;
    cin>>n;
    heapsize=n;

    int a[n];
    printf("The elements are\n");
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    heapsort(a,n);

    printf("After being sorted\n");
    for (int i=1;i<=n;i++)
    {
        //printf("i is %d\n",i);
        cout<<a[i]<<endl;
    }
}

Answer 1

You can use the same heapsort algorithm as before, just replace the less than operator (or greater than if you are using that for comparison) everywhere with a new function:

bool LessThan(int a, int b)
{
  if (a%2 == 1 && b%2 == 0)
     return true;
  if (a%2 == 0 && b%2 == 1)
     return false;
  return a < b;
}