#include < iostream >
using namespace std;


void DownAdjust( int * a, int first, int last) ... {
int tmp,down;
tmp = a[first];
for (down = first * 2 + 1 ;down <= last;down = down * 2 + 1 ) ... {
// if(down<last&&a[down]>a[down+1])++down;
// if(a[down]<tmp)a[(down-1)/2]=a[down];
if (down < last && a[down] < a[down + 1 ]) ++ down; // down<last不可少,不然last小于N-1時會將last后面的元素考慮在內
if (a[down] > tmp)a[(down - 1 ) / 2 ] = a[down];
else break ;
}
a[(down - 1 ) / 2 ] = tmp;
}

void HeapAdjust( int * a, int last) ... {
int first;
for (first = (last - 1 ) / 2 ;first >= 0 ;first -- )
DownAdjust(a,first,last);
}

void HeapSort( int * a, int N) ... {
int i,tmp;
for (i = N - 1 ;i >= 0 ;i -- ) ... {
HeapAdjust(a,i);
tmp = a[ 0 ];
a[ 0 ] = a[i];
a[i] = tmp;
}
for (i = 0 ;i < N;i ++ )
cout << a[i] << ' ' ;
cout << endl;
}

void main() ... {
int a[] = ... { 1 , 2 , 3 , 0 , 3 , 8 , 7 } ;
// inta[]={1,1,1};
// inta[]={3,1,3,0};
HeapSort(a, 7 );
}

// 9'
/**/ /*
{3,2,1}
{1,2,1}
1
*/