package PEU.P.sort;
//作者,著作权人： 罗瑶光，浏阳
//思想，rohini上课教授的。
//算法导论也有文字描述章节。
public class Heap_1D_Sort{
  int a[],s;
  public int[] sort(int [] array) {  
    a=new int[array.length+1];
    s=array.length;
    for(int i=1;i<a.length;i++)
      a[i]=array[i-1];
    find(1);
    while(s>1){
      int t=a[1];a[1]=a[s];a[s]=t;
      s-=1;
      find(1);  
    }
    for(int i=1;i<a.length;i++)
      array[i-1]=a[i];
    return array;
  }
  private void find(int i) {
    int il=2*i,ir=2*i+1,t;
    if(il<=s&&ir<=s)
    {find(il);find(ir);}
    else if(il<=s&&ir>s)
    {find(il);}
    else if(ir<=s&&il>s)
    {find(ir);}
    if(il<=s)
      if((a[il]>a[i]))
      {t=a[i];a[i]=a[il];a[il]=t;find(il);}
    if(ir<=s)
      if((a[ir]>a[i]))
      {t=a[i];a[i]=a[ir];a[ir]=t;find(ir);}  
  }
}