با ساختار heap sort که اشنا هستید ؟؟
اول اعداد رو بگیرید و به ترتیب به اخر ارایه اضافه کنید بعد همونجا تا جایی که میشه رو درخت بیاریدش بالا بعد هم خونه اول ارایه میشه کوچکترین اون میخونید بعد اونو با خونه اخر ارایه swap میکنید و و تا جایی که میشه عدد رو ببرید پایین اگه توضیحات مفهموم نیست کد زیر رو ببینید :
کد :
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=100000+10;
int n,a[MAXN],siz;
void BubbleUp(int n)
{
if(n/2 && a[n]<a[n/2])
{
swap(a[n],a[n/2]);
BubbleUp(n/2);
}
}
void BubbleDown(int n)
{
if(2*n>siz)
return;
else if(2*n==siz)
{
if(a[2*n]<a[n])
{
swap(a[2*n],a[n]);
BubbleDown(2*n);
}
}
else
{
int x=2*n;
if(a[2*n+1]<a[x])
x++;
if(a[n]>a[x])
{
swap(a[n],a[x]);
BubbleDown(x);
}
}
}
int main()
{
cin>>n; /// size of array
for(int i=1;i<=n;i++)
{
cin>>a[i];
BubbleUp(i);
}
siz=n;
for(int i=0;i<n;i++)
{
cout<<a[1]<<' ';
swap(a[1],a[siz]);
siz--;
BubbleDown(1);
}
return 0;
}
اگه سوالی هست در خدمتم