如何使用堆排序先打印奇数顺序,然后再打印偶数而不是较小的数字?
How can I print order of odd numbers first and then even instead of smaller numbers using heapsort?
假设有一个由数字1,2,4,3,5,6,7组成的数组
.我想使用heapsort打印1,3,5,7,2,4,6。
我一直在尝试修改基本堆排序但无法获得正确的输出。
你能帮忙吗?
#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;
}
}
您可以使用与以前相同的堆排序算法,只需将小于运算符(或大于,如果您使用它进行比较)替换为新函数:
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;
}
假设有一个由数字1,2,4,3,5,6,7组成的数组 .我想使用heapsort打印1,3,5,7,2,4,6。 我一直在尝试修改基本堆排序但无法获得正确的输出。
你能帮忙吗?
#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;
}
}
您可以使用与以前相同的堆排序算法,只需将小于运算符(或大于,如果您使用它进行比较)替换为新函数:
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;
}