class heap_sort 
{
public:
 void HeapSort(int a[],int n);
 void swap(int&a,int&b);
 void CreatHeap(int a[],int n);
 void Shift(int a[], int left,int right);
 heap_sort();
 ~heap_sort();

private:
 
};
heap_sort::heap_sort()
{
 a[0]=0;
}
heap_sort::~heap_sort()
{
}
void heap_sort::Shift(int a[], int left, int right)
{
 int x,curr, joint;
 curr=left;
 joint=2*curr+1;
 x=a[curr];
 while (joint<=right)
 {
  if (joint<right)
  if(a[joint]<a[joint+1])
    joint=joint+1;
  if(a[joint]<x)
    break;
  a[curr]=a[joint];
  joint=2*curr+1;
 }
 a[curr]=x;
}
 
void heap_sort::CreatHeap(int a[], int n)
{
 int left;
 for(left=(n-1)/2;left>=0;left--)
  swap(a,a[n-1]);
}
void heap_sort::swap(int &a, int &b)
{
 int tmp=a;
 a=b;
 b=tmp;
}

void heap_sort::HeapSort(int a[], int n)
{
 int right;
 heap_sort::CreatHeap(a,n);
 right=n-1;
 while (right>0)
 {
  swap(a[0],a[right]);
  right--;
  Shift(a,0,right);
 }
}