代码如下:
#include<iostream>
using namespace std;
const long long N=1e6+1;
long long n,a[N];
long long dtrimin(long long x,long long y,long long z)
{
if( x<y && x<z) return 1;
if( y<x && y<z) return 2;
return 3;
}
void resort(long long x)
{
if(x*2>n) return;
if(x*2 == n)
{
if(a[x*2]<a[x]) swap(a[x],a[x*2]);
return;
}
switch(dtrimin(a[x],a[x*2],a[x*2+1]))
{
case 1 :
return;
case 2 :
swap(a[x],a[x*2]);
resort(x*2);
break;
case 3 :
swap(a[x],a[x*2+1]);
resort(x*2+1);
break;
}
return;
}
void insert(long long x) // 仅供参考 , 本程序没用到
{
a[++n]=x; long long poi=n;
while(poi>1)
{
if(a[poi/2]<a[poi]) break;
swap(a[poi/2],a[poi]); poi/=2;
}
return;
}
void Make_heap()
{
for(long long i=n;i;--i) resort(i);
return;
}
long long find_and_delate()
{
long long qans=a[1];
swap(a[1],a[n]); --n;
resort(1);
return qans;
}
int main()
{
cin>>n;
for(long long i=1;i<=n;++i) cin>>a[i];
Make_heap(); // 建立小根堆
for(;n;) cout<<find_and_delate()<<" "; cout<<endl;
//system("pause");
return 0;
}