/**
  *堆排序思路：O(nlogn)
  *    用最大堆，传入一个数组，先用数组建堆，维护堆的性质
  *    再把第一个数与堆最后一个数调换，因为第一个数是最大的
  *    把堆的大小减小一
  *    再  在堆的大小上维护堆的性质
  *    重复操作..
  *
  *
  */
 public  class  HeapSort
 {
     /**
      *静态变量存放堆的大小
      */
     private  static  int  heapsize = 0 ;    

     /**
      *堆排序主方法
      *    构建最大堆，然后进行堆排序
      *    堆排序是把最上面的最大的元素放在最下面，然后再维护上面最大堆的性质
      */
     public  static  void  heapSort(int[] resouceArr)
     {
         //堆的大小
         heapsize = resouceArr.length - 1 ;

         _buildMaxHeap(resouceArr);

         for( int i = resouceArr.length - 1 ; i >= 0 ; i--)
         {
             int temp = resouceArr[0] ;
             resouceArr[0] = resouceArr[i] ;
             resouceArr[i] = temp ; 

             heapsize = heapsize - 1 ;
             _maxHeapify( resouceArr, 0 );
         }
     }

     /**
      *构建最大堆
      *    构建之后还不是有序的，但符合最大堆性质，上面的数一定大于下面的数
      */
     private  static  void  _buildMaxHeap(int[] arr)
     {
         int length = arr.length - 1 ; 

         //从倒数第二排开始维护最大堆性质
         //    当heapsize为偶数时，heapsize要减一
         //    当heapsize为奇数时，不变
         if(length % 2 == 0)
         {
             length--;
         }
         for( int i = length / 2 ; i >= 0  ; i--)
         {
             _maxHeapify(arr , i );
         }
     }

     /**
      *用于维护堆的性质
      *    树形堆在postion的位置向下维护堆的性质，自postion向下满足最大堆的性质
      */
     private  static  void  _maxHeapify(int[] arr,int postion)
     {
         //计算postion的左孩子和右孩子
         postion = postion + 1 ;

         int  l = postion * 2 - 1;
         int  r = postion * 2 ;
         postion = postion - 1 ;

         int largest = maxNumInThreeNum(arr , postion , l , r);

         //如果不满足最大堆性质，则交换值，然后检查树形下方是否满足最大堆性质
         if(largest <= heapsize)
         {
             if( largest != postion)
             {
                 //交换最大值与父节点值
                 int  temp = arr[postion] ;
                 arr[postion] = arr[largest] ;
                 arr[largest] = temp ;
                 //如果子节点变动了，则重新构建已子节点为根的最大堆
                 _maxHeapify(arr , largest);                

             }
         }
     }    

     /**
      *比较数组中的三个数找出最大值
      */
     private  static  int  maxNumInThreeNum(int[] arr ,int a, int b , int c)
     {
         int max = a ;
         //数组长度小于左孩子，最大值为本身
         if(heapsize < b)
         {
             max = a ;
         }
         else if(heapsize >=b && heapsize < c)
         {
             if(arr[a] < arr[b])
             {
                 max = b ;
             }
         }
         else
         {
             if(arr[a] > arr[b])
             {
                 max = a ;
             }
             else
             {
                 max = b ;
             }
             if(arr[max] < arr[c])
             {
                 max = c ;
             }
         }
         return max ;
     }
 }