Pagini recente » Cod sursa (job #1025345) | Cod sursa (job #2416481) | Cod sursa (job #2681212) | Cod sursa (job #463436) | Cod sursa (job #1877180)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("algsort.in");
ofstream fout("algsort.out");
int a[500005],n,auxn;
void read()
{
fin>>n;
for(int i=0;i<n;i++)
fin>>a[i];
auxn=n;
}
void heapify(int i)
{
int largest,lc,rc;
lc=2*i+1;
rc=2*i+2;
largest=i;
if(lc<n&&a[lc]>a[largest])
largest=lc;
if(rc<n&&a[rc]>a[largest])
largest=rc;
if(largest!=i)
{
swap(a[largest],a[i]);
heapify(largest);
}
}
void write()
{
for(int i=0;i<n;i++)
fout<<a[i]<<" ";
fout<<"\n";
}
void makeHeap()
{
for(int i=n/2-1;i>=0;i--)
heapify(i);
}
void heapSort()
{
makeHeap();
//write();
while(n>1)
{
swap(a[0],a[n-1]);
n--;
heapify(0);
}
n=auxn;
}
int main()
{
read();
heapSort();
write();
return 0;
}